Rule over the chaos on the Sharp edge

2023-01-22

In the previous post, we have covered the usage of sub-$5 clones of Sharp EL-506P to do lots of things, even valid IMEI generation, and pointed out some features that make this platform a great hacker’s assistant overall. Now, it’s time to do some even more advanced stuff: how about a whole friggin’ stream cipher?

The backstory

Yeah, I wish I knew more about the PRNG already present in this calculator but for now, no new information has popped up. So we’ll have to recreate a more or less secure PRNG on this machine ourselves. Not only that, but we’ll try to optimize it for as few keystrokes as possible. The idea of what I’m about to describe is based on what I had read in an article (by Francisco Ruiz) that, unfortunately, now only lives on the Web Archive, but I wanted to break it down to the basic principles and use somewhat more suitable functions available in the EL-506P and hence my KS-105B, taking full advantage of its 12-digit internal precision despite it only can display 10 decimal places at once. And, since this is a stream cipher we’re talking about, we can be sure the generated pseudorandom keystream is going to be identical on both sides as long as they use the same keys, sequence numbers and the calculator platform, be it the original EL-506P, Citizen SR-135N or this cheap Kenko.

So, basically, the original idea in that article was to first break your decimal session key (that consists of the initial passkey number and the message ID) into three groups of digits whose size is equal to the calculator’s resolution. You can also use a longer passkey and create 5 groups of digits, 7, 9 and so on. The final group is fully assigned to the fractional part (so that it’s a floating point number from 0 to 1) and used as an initial seed (S[0]). Aside from it, every first group is split in half places by the decimal dot and, in this way, used as a multiplier (M[i]), and every second group is split in (half - 2) places by the decimal dot and, in this way, is used as an adder (A[i]). And for the N sets of multipliers and adders, the formula to calculate the next seed and the keystream digits (KS) is:

S[i+1] = fract(sqrt(S[i] * M[0] + A[0]))
S[i+2] = fract(sqrt(S[i+1] * M[1] + A[1]))
...
S[i+N] = fract(sqrt(S[i+N-1] * M[N-1] + A[N-1]))
KS = S[i+N] * 10^(calc res)

I.e. the new keystream output consists of all the digits of the last seed S[i+N] after the decimal dot. Then the process is repeated until all the keystream digits of the required length are recovered.

I hope you get the main principle here: a nonlinear transformation (in our case, a fraction of the square root) that maps a simple linear polynomial value to a new irrational number (or at least a number expected to be irrational) from 0 to 1. This algorithm is nice as it is when both of you have a normal desktop calculator that really can, as recommended by the author, display 12 or even 14 digits but only has a square root function available. But even then, you’ll have to do the fract part manually by subtracting the integer part, and the internal precision of the calculator will take care of the lowermost digits. However, here we’re dealing with a 10-digit machine that has a 12-digit internal precision but is a scientific calculator, so it has some nice functions we can really substitute the square root and fraction combo with, as they can already map any real value to the range between -1 and 1 (which is even better than the 0 to 1 range as it allows us exploit the negative number space just as well). And because of that, it doesn’t even matter where we put the decimal dots in the adder or multiplier parts. Yes, I’m talking about the sine and cosine functions when used in radians mode. So, the simplest modification of the formulas above would be:

S[i+1] = sin(S[i] * M[0] + A[0])
S[i+2] = sin(S[i+1] * M[1] + A[1])
...
S[i+N] = sin(S[i+N-1] * M[N-1] + A[N-1])
KS = |S[i+N]| * 10^(calc res)

Note that you can use cos function instead at any step, it, of course, will affect the value of the keystream but won’t affect its properties. Just make sure your calculator’s DRG setting is set to radians and you’ll be fine.

Now, let’s try to get rid of the multipliers so that our key material only spreads out across the adders, and also make the adders fully fractional like the seed (so that they represent a value from 0 to 1), but introduce some additional irrationality to the arguments by using the constant of π (that we have handy in our calculator models by using 2ndf EXP combo) to use on the whole argument expression instead of the multipliers:

S[i+1] = sin(π * (S[i] + A[0]))
S[i+2] = sin(π * (S[i+1] + A[1]))
...
S[i+N] = sin(π * (S[i+N-1] + A[N-1]))
KS = |S[i+N]| * 10^(calc res)

Doesn’t this already remind you of something? Well, if we remove the adders and leave the transformation unkeyed and only dependent on its initial state, we’ll get a partial case of the sine chaotic map x[i+1] = μ * sin(π * x[i]) with the value of μ hardcoded to 1. And it’s totally fine that it’s hardcoded because the sine function’s chaotic behavior is best displayed at this value here. The adders though still are necessary to make the keystream 1) constantly dependent on the key and not predictable even if an intermediate KS value is known, 2) not tending to some stability points which would make the distribution of digits far from uniform. I also like the Ruiz’s idea at the end of the article to generate a session key based on the master key and message ID, not just using them directly. However, here’s my final touch to the algorithm: even with all these precautions, I would only use the lower half of the resulting state digits. E.g. if the final state value on my 10-digit Kenko turned out to be 0.123456789, I’d only use 56789 as my output keystream digits. This will make it virtually impossible to recover the internal PRNG state even if this portion somehow becomes available to the attacker.

By the way, at this point, you can substitute π with 180 and use the degrees mode instead if you’re comfortable with hitting one more key to type 180 instead of 2ndf π. If you store the value, be it π or 180, in the memory register though, it doesn’t really matter, it’s only one RM hit anyway.

So, let’s fully reiterate the final version of the keystream generation algorithm (that I have named Chaosine) in a more formal way and then look at an example of what we actually enter to the calculator at each step.

The Chaosine PRNG algorithm

Requirements: two platform-identical scientific calculators (for the sender and the receiver) with 10-digit or better precision (let’s denote the number of digits P), sine function and π constant available with radians mode (or, alternatively, the capability to switch to the degrees mode).

R operation definition

Inputs: state number S (in the range [0,1]), array of adders A0..An (each in the range [0,1]).

Output: new state number S.

Process:

For each adder Ai in the input, perform the following calculation: S = sin(π * (S + Ai)). Replace π with 180 in this formula if operating in the degrees mode.
Return S.

Main algorithm definition

Inputs: message length L, a master key MK and the message ID MID. The MID must be unique to each message. All inputs must be encoded as plain decimal digits. The total length of MK and MID combined must be divisible by P-1.

Output: the resulting keystream KS of the length L.

Process:

Concatenate MK and MID into a string of digits. Split this string into the GN groups of P-1 digits. Convert every group into a floating point number in the [0,1] interval by prepending 0 and decimal point.
Perform the R operation (defined above) on these numbers using the last one as the S state value and the rest of them as the Ai adder values. Use the new S value as an input to the new R operation. Repeat this step until you have GN new S values. The list of these values is your session key SK.
Use the last value in the SK list as the current S value, and store the rest as the adders list AL. Set the KS output to empty.
Perform the R operation on the S value and AL list, and store the result as the new S value. Take exactly P/2 lower digits from the S value (including the trailing zeros, if any) and append them to the KS output. Repeat this step until KS output contains L digits.
Return the keystream KS.

Example

While the formal definition might look intimidating, the algorithm actually is very simple to implement. Let’s imagine we have our EL-506P clone with 10-digit display and we need to encrypt a 40-digit-long message. So, this means that the L parameter in our case is 40, and the value of P is 10. Let’s also imagine that we have a 21-digit master key (not hard to generate using the same calculator) which leaves us 6 digits for the message ID number for the total length to be divisible by P-1 = 9. So, our input parameters are:

L: 40
P: 10
MID: 000001
MK: 781983614135120768683

Now, the first thing to do is combine MK and MID and split it into 9-digit groups:

1
2
3

781983614
135120768
683000001

As you can see, we get 3 groups, so our GN value is 3. This gives us 3 floating point numbers: 0.781983614, 0.135120768 and 0.683000001. Now, we use the latter as the seed S and the former two as the adders Ai as the input to our R operation. Here’s where the calculator kicks in:

1 2	.683000001 + .781983614 = × 2ndf π = sin + .135120768 = × 2ndf π = sin

This is how I get the first new S value, -0.429089371. Now, I need two more so I repeat the process:

1 2	+ .781983614 = × 2ndf π = sin + .135120768 = × 2ndf π = sin

And the next value is -0.09506295. Now, let’s find out the last one:

1 2	+ .781983614 = × 2ndf π = sin + .135120768 = × 2ndf π = sin

And the third value is 0.101611422. We’ve reached the GN of 3 groups, so these three values, -0.429089371, -0.09506295 and 0.101611422, are our session key. And we use the last one (still in our calculator’s buffer btw) as the seed for the next calculations, which is very convenient. Now, continue repeating the following sequence until we get all the required digits out of it:

1 2	- .429089371 = × 2ndf π = sin - .09506295 = × 2ndf π = sin

The first iteration (remember, we only take P/2 lower digits, which is 5 in this case) gave me 18381, the second gave 61095, and so on. Let’s write down the 40-digit sequence I’ve got from this:

1 2	18381 61095 10493 90139 19090 70078 08348 89158

And this, ladies and gentlemen, is our keystream KS for this particular message. The receiver(s), knowing the message ID and the master key, will repeat the same process using the same equipment and get the same keystream on their end. Obviously, if your calculator is programmable at least to some extent, e.g. a Citizen SRP-145 or a Casio with the Program-FX feature (like the FX-3400P or something not so rare), the process can be made much faster, you just need to make sure the receiving end has the same calculator model/platform.

The full cryptosystem

Now, generating a keystream is only a part of the story. After all, it can only be of any use if we encrypt some information with it. But in order to do this, both the information and the keystream need to be converted to the same format first. So, there are several options on what we can do with these digits, as well as how we encode the messages themselves.

Option 1: leave the keystream in the form of digits and encode the message to digits as well. This also leaves us with some options — either use the original Ruiz’s suggestion to encode every character to a 2-digit value, which I personally consider a bit excessive, or use something like a straddling checkerboard for your alphabet to encode messages in a more optimal fashion. This leaves us with less message digits to deal with and thus less keystream digits required to be calculated. But then, regardless of how we choose to encode the message, this will also mean the need to perform manual addition (or subtraction) modulo 10 of every message/ciphertext digit while encrypting/decrypting. This might not require a calculator but takes plenty of time even for the shortest messages.

Option 2: leave the messages in their original alphabet (probably a reduced one) but convert the keystream to this alphabet too, and then just use a printed tabula recta (I prefer something like the Perfect Light version) for fast addition and subtraction of characters themselves. To me, this sounds like a much more viable and practical option to use with Chaosine, as well as with any other symmetrical pen-and-paper or calculator-assisted encryption algorithms. Even if you don’t have a printed tabula recta, you can always draw your own in a notebook. The only remaining question is: how do we convert the keystream digits into the target alphabet so that we don’t make it too difficult to perform “on the fly” yet preserve the uniform distribution of characters, however many we’re going to have in that alphabet?

Well, again, there may be several answers to this question, and the answer I chose might be the most straightforward and easy to use, especially once it’s tabulated. “Alphabetizing” the keystream is a unidirectional process, so, here we can afford something we couldn’t afford with the plaintext/ciphertext conversions. So, if we assume to use a 26-letter Latin alphabet with the Perfect Light tabula recta, we need to find a way to map 10 digits (or their group) to 26 characters with as little bias/loss as possible. To do that, we just take the pairs of the keystream digits and multiply each pair by (L/100), where L is the alphabet size. So, in our case, it’s 0.26. Then the integer part of the result will show our encoded letter. But then, with this approach, we are mapping several pair of digits to the same letter, so we also need to output a small carryover number that we add to the next letter (modulo L) after encoding the next pair of digits. All this can be easily tabulated for a fixed alphabet and then used in a printed form along with the corresponding tabula recta. The carryover number C from the last character encoded, if it’s non-zero, is then applied to modify the very first character of the output keystream the same way, by shifting it by C positions to the right in the target alphabet.

That’s it. Obviously, this scheme isn’t perfect and doesn’t eliminate the bias coming from the fact that we’re mapping 100 different values to 26 and that sometimes, because of that, only three of these values will map to the same letter instead of four, so the maximum carryover number will be 2 and not 3 (remember, we’re starting from 0) in such cases. The distribution can be made more uniform though if we switch to a 25-letter alphabet (traditionally, that was done by mapping I and J or C and K or K and Q as the same letter). This way, exactly every four values map to the same letter, every carryover number can be from 0 to 3 and has an equal (exactly 1/4) probability of appearing in the stream. The same properties will be observed if our alphabet consists of 50 characters, just the carryover number will be either 0 or 1 in this case. For the generic purposes, our 50-character alphabet can consist of: 26 basic Latin letters (A-Z), 10 digits (0-9), whitespace and 13 special characters (. , ? : ( ) + - * / # @ $). The choice of special characters is such as to allow to abbreviate most commonly used expressions without making them too cryptic and far away from the natural language, with @ used as “at”, # used as “number of/amount of”, + used as “and” or “extra” and so on. E.g. the sentence “We’re going to supply extra 6 units of equipment for the price of 20.39 USD each at 7:30 PM tomorrow, meet us at place A” can be abbreviated as GONNA BRING +6 EQUIP $20.39/EACH TMRW@1930,MEET@A string which still can be easily read by a human but is only 49 characters long so more suitable for manual encryption than the initial message. This is why I also highly recommend to use a 50-character alphabet (and the corresponding tabula recta) over a 25-character alphabet: the tables are larger but it allows for much shorter messages to convey the same information, so you save a lot of time on encoding/decoding.

So, to reiterate once more, the full Chaosine cryptosystem consists of:

The Chaosine PRNG algorithm itself to generate the keystream using a scientific calculator (described above).
The (printed) digit-to-character conversion chart to quickly map every pair of keystream digits to a character of the target 25/50-character alphabet and to a carryover number from 0 to 3 in case of 25 characters and from 0 to 1 in case of 50 characters, and the rule to apply the carryover number to the next or the first keystream letter.
The (printed) tabula recta for the target alphabet to perform fast addition/subtraction of its characters.

Note that all this is just a specification draft, I guess I’ll publish the finalized version in the PDF format at some point in the future, including all the printable materials there, tailored to a 50-character alphabet.

Bonus content: the Chaosquare PRNG algorithm

Now, imagine a situation where you don’t even have time or possibility to grab several identical KK-105’s or other scientific models and distribute them across all communication parties, and all of you are stuck with the generic 8-digit-display, 8-digit-precision sub-$1 calculators (like KK-402), some of which might not even necessarily have a square root function or even a memory register (although that’s a rare situation nowadays, but some examples like the Casio CA-53W watch are quite popular). What can we do to generate the keystream in this case?

Well, the first thought is to find a way to switch from the chaotic sine map to the most chaotic case of logistic map while also keeping it parameterized with the numbers derived from our session key. So, our R(S, A0..An) operation in the above algorithm can be modified to something like S = |4 * S * (1 - S) + Ai - 1| for each Ai value. And in this case, we can obviously only generate 4 keystream digits at a time using our model. Now, how do we optimize this operation in terms of keystrokes?

Here’s where we need to know two tricks one can use on these cheapos that don’t even obey any precedence rules. The first trick we need to know is the fact that here, depending on the operation we perform, either the first (if the operation is ×) or the second (for all others) operand still is stored in a special buffer along with the operation performed and is reused in the context of the operation we’re currently entering (i.e. as the first operand for multiplication and as the second one for everything else) if we don’t explicitly input the other operand before pressing = afterwards, so the sequence A × = - = will actually calculate the value of A - A², which is exactly what we need. The second trick is how to invert the sign of your result, something done with a single +/- key on the scientific calcs, if your noname 8-digit simple calc doesn’t have this key. First, we need to clear that buffer by pressing + 0, second, we just press - = to perform the 0 - X operation, and third, we clear the buffer once more by pressing + 0 =. So, the sequence to invert the sign without affecting the further chain of calcualtions is: + 0 - = + 0 =. Alternatively, since our goal is to find the absolute value, if your calculator does have a square root function, you could use something like × = √ + 0 =, but I don’t recommend it anyway because you might lose some more precision while doing these operations.

That’s why, using these tricks and provided the state value already is on the display, the R operation can be expressed on such calculators as follows: × = - = × 4 + Ai - 1 + 0 =, and then, if the result is below zero, we also need to press - = + 0 = afterwards. This makes it 17 to 22 keystrokes long, not counting the Ai number entry itself. And the state is ready for the next iteration. Note that for the CA-53W and other exotic cases with explicit constant mode, the keystroke sequence will be a little different but the principles of operation remain the same.

Other than this R calculation step, every other bit of Chaosine PRNG algorithm and the whole system remains unchanged. I’m calling this modification Chaosquare, because the square function in the logistic map is the main nonlinear element to provide pseudorandom properties. I think this modification will be published along with the main Chaosine system in the same printable material. Until then, I’m going to take a little break from these little machines and will turn to some other but no less interesting topics. See ya!

#encryption #calculator #cryptography #stream cipher #chaos #chaotic map