Research and architecture ideas for maths editor

I've been working on a personal project that I'm quite fond of, and it's taken probably the most research and generally just thinking about how to approach each section of any project I've ever taken up. As such I wanted to write out my thoughts on how I structured and designed the workings of the program here.

The program itself is essentially a text editor made specifically for mathematical expressions. I've always found it frustrating that I chose one of the few subjects at university that still require a pen and paper (that is, physics), while everyone else gets to use laptops, so I've decided to try and solve the problem of writing and handling mathematical expressions being much harder on a keyboard than on paper with this program. The core idea is that from a terminal with ncurses you can use a set of keybinds to write an arbitrary expression out in free form quickly and easily, then switch to 'operation mode, much like default/insert mode in vim, to use a new set of keybinds to carry out operations that follow mathematical law on your written expression. The program automatically simplifies expression for you, so if your expression is simply 'x' and you add an x, it'll know to present the resulting expression as '2x', rather than 'x+x'. Likewise if you add a y, you'll be left with 'x+y'. It should be noted that this is not wolframalpha though - you cannot ask it to *solve* mathematical equations for you, by making certain variables the subject or finding roots etc. You still do all of the working out, as you would on paper, the goal here is that when you command an operation to be done, the equation that's returned is the same as what you would had wrote if you were writing it yourself on paper.

So lets get into the details of how this can be done. Currently only the backend is being worked on before the interface is started, so this will only deal with how that works, however I'll come back and add to this blog as more progress is made.

What we're essentially writing is a basic interpreter. We need something that can take an arbitrary string, cut it down into component parts (it's tokens), figure out how these tokens are to be parsed and then carry evaluation. The tokeniser is simple, as it just needs to spit out numbers, variables and operators as it sees them. The only real job is to collect whole numbers as one token, so that '10+5' is returned as '10', '+', '5' rather than '1', '0', '+', '5', but this too is trivial. It also needs to add in implicit operations left out by common short hand such as '10x', so that '10', '*', 'x' is returned, but this is again trivial.

Once we have our tokens then it's a matter of figuring out how to parse them. In interpreters for languages, an abstract syntax tree is used, so lets use something like that. Maths is very simple in this respect and so a parse tree is a natural choice, where each binary operator like a plus has two children which can either be numbers, variables or more operators that eventually terminate with numbers or variables. This of course changes slightly for more advanced operations, like trig or log functions, but they are only unary operators rather than binary, so they would just have one child instead of two. Likewise calculus operations can be considered unary operations. However, the core of the program is first being build with only 'basic' algebra in mind, as to simply work as a proof of concept for the approach being taken.
I've drawn out examples of what the tree should look like given a typical expression:

It's parsed simply by taking the bottom leaves, applying the operator stored in their parent, then replacing the key in that parent node with the result. and recursively doing so until only the root node and therefore result of the operation remains.

However, we're getting ahead of ourselves here. Before we can parse the tree, we need to build it from a stream of tokens. This was initially quite difficult to think about as how could you cleanly take an arbitrary expression like the one seen at the top of the above picture, and construct a tree that when parsed would evaluate the expression in the correct order according to operator precedence? There seems to be no obvious way, based on an *in*fix expression at least. What we can do to make life easier is convert our given equation to *post*fix (aka reverse polish notation) and then simply build the tree recursively using a modified shunting-yard algorithm for postfix expression evaluation, the modification here of course being rather than direct evaluation - which the shunting-yard algorithm isn't equipped for when dealing with algebraic variables - simply constructing a parse tree instead. What makes postfix notation perfect is that it already contains the correct evaluation precedence within it, so brackets don't ever need to be used, meaning you can add nodes to a tree directly rather than having to on the fly deal with bracketing order. I did think about how this could be possible, but also so much more of a mess that the extra step to convert to postfix notation is certainly worth it. It's also worth noting though that what's great about how the parse tree is constructed is that even though brackets are lost in postfix conversion, they can be recovered in the resulting evaluated expression by adding them back in to the rest of what's already been evaluated whenever the next operator seen has a higher evaluation precedence than the previous one. 

So, we have our parse tree constructed in a beautiful and recursive fashion thanks for postfix notation, now for the meaty part of actual evaluation, and where this program in my mind becomes unique. Every term involved in the parse tree - regular numbers, variables or a mix - can be split into three distinct parts: the variable, the coefficient and the exponent. The variable and exponent parts are the determining factors on if combination is possible, while coefficients are just regular numbers and can be operated on each other at will. As such using a 'term' class for every token seems like the best idea, that can store all this information as it gets manipulated over the evaluation and used for checking for simplification opportunities. However things get more complicated when you can't combine two terms and have to leave operators in - for instance the 'x+y' example gave earlier. This case can be tackled in a similar fashion though, it's just a collection of terms, and can be treated like it's own term in evaluation. As such container classes can be used to store different incompatible terms and which operators are connecting them, and when these container terms are evaluated they too can be added to larger container terms, where each term can be retrieved recursively. For instance, 'x*(x+1)' will iterate over the container term '(x+1)' and multiply 'x' to every individual term inside - 'x' and '1'.

I believe the core idea of this part to be solid, however currently there are still some implementation issues I'm considering. Namely, the best way to actually structure these container term classes that makes them easiest to parse. My initial idea was to hold separate variables in the class for numerator, denominator and exponent, but this causes evaluation to get messy with a lot of condition checks required at every turn, so I'm thinking there should be a better and cleaner way to approach this, which is currently where I'm at on this project. I will be excited to update this post as new advancements in the program comes along, though!

HackTheBox Challenge: Weak RSA

This challenge was very important to breaking me into crypto and handling of binary data. The intended way, due to it being an easy level challenge, was to read up on wikipedia about RSA, find out about the existence of the wiener attack, then download a script to run on the given ciphertext to extract the flag. I however assumed it was intended to be exploited from scratch, so I ended up spending far more time than was expected on creating my own python script (with help of a guide on how the wiener attack works) to complete the challenge, and I’m glad I did! The process introduced me to a lot of new concepts that I’ve then been able to use to make harder crypto challenges much easier, and will undoubtedly be useful for future programming projects.

The challenge itself simply gives you a ciphertext and an ascii armored public key, you have to figure out the rest. To me at the time this was quite a lot, as I didn’t really understand the differences between the three major crypto functions (symmetric, asymmetric, one-way compression) to begin with, let alone the details on how they worked. Luckily in comparison to the others, RSA has fairly straight forward internal workings, as it just relies on a small system of equations, rather than a large internal and complicated process like block ciphers or hash functions.

Using a package called pyCrypto I could import the given public key and print it’s public exponent and modulus. I created a small script just to have handy so I could quickly reread the values whenever needed.

After becoming familiar with the fundamentals of RSA and getting a way to access the public key’s elements directly, I started looking into common attack methods on wikipedia. The first was about how that for encryption carried out with a small public exponent (e), say around 3, the original plaintext could be retrieved from the ciphertext by simply taking it’s e’th root. Now as we can see, the public exponent used here was very large, and so this attack wouldn’t be feasible, however this did strike me as odd - how can you take the root of a text file? Well, in the same way RSA itself is applied to any type of text – by breaking it down into one single number and applying the mathematical equations on it, and this was the first time I really realized the know seemingly obvious fact that everything is just a bunch of numbers. Furthermore, with a bit of research and asking around, I also learnt about the algorithms OS2IP (octet stream to integer primitive) and I2OSP (integer to octet stream primitive) which can take either strings of text or whole numbers respectively and convert them from one to the other, which are obviously vital in an RSA encryption and decryption process.

Armed with this new knowledge the next challenge was dealing with encoding and decoding of text data using Python. This was again a new area to me but obviously very important in crytpo and programming generally. A big hurdle was simply realizing that data is actually ‘encoded' when it’s in raw byte form, and ‘decoded’ when in ascii/unicode, at least by python’s definitions anyway. Figuring out when to work with bytes and when to work with characters, when to use little or big endian (another concept I only came across due to this challenge) and also how to encode bytes back to unicode correctly in a preserving format – it turns out printing or piping from stdout to say the base64 utility will discard all non-printable characters and thus alter the data you’re working with. This happens with both Python and C! So, to get around that you also have to encode your bytes to base64 while they’re still in the memory of the program itself, rather than piping through stdout to the base64 tool, and then all your data will be preserved and can be reopened in the same way. This is all unrelated from crypto directly, but if you’re to write programs to carry out exploits from scratch is still vital knowledge that I had no idea about before attempting this.

Eventually I came across the wiener attack and realized that must be the one, as nothing else had worked so far. Learning about the maths was fun, and implementing it in python was fairly trivial.

Though messy, the output of our script contains our flag!

I came out of this now knowing about the internal workings of RSA, how encryption carries out mathematical operations on text, and how to properly handle encoded data to be manipulated or outputted in a program. Even though it was the ‘easiest of the challenges I’ve done, it probably took the longest and taught me the most!