RSA encryption - a warning!

I should perhaps at this point warn people not to try to use any of what I have described in my last few blogs about this subject to actually encrypt anything of value. This is all for demonstration purposes to illustrate the mathematics and computing of RSA. It is not for real world situations! If you need to encrypt anything please use a reputable program!

RSA Encryption - another example and discussion

Following on from my previous blog I thought I would encrypt a message that you out there can have a go at decrypting. Here it is: 331, 230, 230, 311, 392, 507, 180, 221, 187, 466, 283, 392, 442, 230, 127. The key information is n=551 and e=41. This should be enough for you to decrypt this message.

Of course with a programmable calculator there is a limit to what you can usefully do with RSA. One of the problems of the fx-50F is that there isn't a function which can do modulo arithmetic and nor  is there a way to find integer parts and remainders on division, and so the ways round this (the while loops in my exponentiation mod n program) make processing much too slow when n becomes larger than a 1000 or so. Hence, this doesn't make the encryption viable unless the keys are hidden.

In reality there is also the issue of finding two primes for n. You don't want to choose one of the primes to be large and the other small, as the small prime will easily be found as a factor in n. However, you also don't want to choose two primes that are very close in value because, as we shall see, n can again be factored quite quickly. So we need two similarly large primes that are not too close in value to make RSA work.

There are other issues as well. We don't want to have the message number m larger than n. Suppose we have the system as set up in my previous example and encrypt m=250, that is we want 250¹³ (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133¹³³ (mod 221) we find m=29. That's because 250 is congruent to 29 modulo 221. So we don't get a one-to-one relationship.

If we choose much bigger primes, n becomes sufficiently large that we can start encrypting blocks of text. For example, in the message 'all aliens are friendly' we could take the word 'all' and convert it into a single number 11212. The next three characters ' al' would be 270112 etc.

Finally, in some situations we find that the encrypted message number m' and the message number m end up being the same and this may be something to avoid.

RSA Encryption - an example

Following my previous blog about RSA encryption let's now try and encrypt the message 'all aliens are friendly'.

Using the Is it prime? program, we can choose a couple of prime numbers. We try some relatively small numbers 13 and 17 which you can easily verify are both prime. Run the Is it prime? program. X? is displayed. Enter 13 and press [EXE]. 1 is returned (1 - number is prime, 0 - number is not prime). So our number n=13x17=221 and φ(221)=(p₁-1)(p₂-1)=12x16=192.

Next we choose e. We choose e=13 and using the program gcd by subtraction you can verify that gcd(13,192)=1. Run the program. A? is displayed. Enter 13 and press [EXE]. B? is displayed. Enter 192 and press [EXE]. The result 1 is displayed indicating that the gcd(13,192)=1.

Next we calculate d which is the inverse of e modulo 192. Run the program Multiplicative inverses in Zn. A? is displayed. Enter 13 and press [EXE]. B? is displayed so enter 192 and press [EXE]. After a bit of a wait the result of 133 is displayed. So d=133.

So now we can encrypt the message 'all aliens are friendly'. The letter a corresponds to 1 and we can see immediately that m'=1 since 1¹³≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡12¹³(mod 221). Run the Exponentiation mod n program. X? is displayed. Enter 12 and press [EXE]. A? is displayed. Enter 13 and press [EXE]. B? is displayed, so enter 221 and press [EXE]. The result is 116 and this is m'. Thus so far the encrypted message is in numbers 1, 116, 116 for the word 'all'.

Continuing in this way we can obtain the full encrypted message 1, 116, 116, 79, 1, 116, 178, 122, 209, 32, 79, 1, 18, 122, 79, 214, 18, 122, 209, 4, 116, 77.

To decrypt the message we need to take each number m' in the encrypted message and calculate m≡(m')¹³³ (mod 221) which again you can use the Exponentiation mod n program to do.

RSA Encryption

Having written these four programs for the fx-50F:-

1. Multiplicative inverses in Zn
2. Is it prime?
3. gcd by subtraction
4. Exponentiation mod n

I am now in a position to be able to demonstrate one of the most widely used encryption methods on the web, RSA. The RSA cryptosystem was first described by Ron Rivest, Adi Shamir and Leonard Adleman in 1978. The complexity of decrypting, i.e. reading an encrypted message using RSA relies heavily on the difficulty of finding the prime factors of very large numbers. For example, if p₁ and p₂ are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p₁p₂=209365018607 but it would be relatively difficult to find their original factors if only the product was known. In the actual implementation of this system prime numbers of typically hundreds of decimal digits are used.

Here is a prescription for using RSA.

1. Choose two prime numbers p₁ and p₂
2. Calculate n=p₁p₂ and φ(n)=(p₁-1)(p₂-1)
3. Choose a positive integer encryption exponent e such that e is less than φ(n) and the gcd(e,φ(n))=1
4. Calculate the decryption exponent d which is the inverse of e modulo φ(n), that is ed≡1 (mod φ(n))
5. To encrypt a positive integer message m calculate m' where m'≡m^e (mod n)
6. To decrypt message m' calculate m≡(m')^d (mod n)

φ(n) is Euler's phi function and is the number of positive integers less than n that are coprime to n. If we have some plaintext message such as 'all aliens are friendly' then one method for encryption using RSA is to take each letter at a time, and encrypt it's numeric position in the alphabet (where 1=a, 2=b, etc). A space ' ' could be given designation 27.

This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p₁ and p₂ (and hence φ(n) and d) private. By doing so anyone can send an encrypted message to the receiver but only the receiver (hopefully) can decrypt the messages.

Exponentiation mod n - execution of the program

In my previous post I detailed a program for finding remainders when a number like 67¹¹ is divided by 41. In my first post I showed that 67¹¹ is the 21 digit number 122130132904968017083 and the remainder on dividing by 41 is 12. On executing the program the display shows X? Enter 67 and press [EXE]. Next A? is displayed and this is the index, so enter 11 and press [EXE]. Then enter the divisor 41 when B? is displayed. On pressing [EXE] again the calculator computes the remainder D and this is shown as 12, which is as expected. Pressing [EXE] again allows another set of numbers to be entered.

If we didn't know what the number 67¹¹ looks like we could at least determine what its last two digits were by replacing the divisor B in the above with 100. When we do this the program calculates the remainder as 83 as expected.

The program is surprisingly fast even for what are very large numbers. For example 67⁶¹⁷ is the 1,127 digit number (from WolframAlpha)

48770057363439563967134348355325038065481286153662007642823470550486

71980560027835524800048781488164580806474123084454431777128171666866

18607377904496236891798400886042117666614291800426648265371610864835

40929572898386140596732260223574328368309073158031647754279482918284

65663724881612657390133487402742747112192939724971784183405095503257

69918877553469511522677242675385108662437741711997020059606722804142

09675268052772569724085754968798539106891583795237329222561781805522

85062589820240643630480393850097329533051647302120862011637881575053

71309698184194685080288379701970330799370917504675997998122640686686

98423317552437389277363219335647530610628399241914162225364781445082

70644504402991235669883493855155234017024331172877674569648340943127

70360444117552920156878524196353157664201104105212692362637491637938

54079014668035647988158392840059044333758548155163870985659977545610

52000559917423988628809593315580421167977682921477636773152575740312

22156667453352073011960706603866023551139632454252812187342672444656

55949111316392732278972914732349074457742403565481714331119758806068

559399641911405354923544154126627269027

However, using the fx-50F program we can determine that the last digit of this number is 7 in only a few seconds (this is 67⁶¹⁷mod 10).

Exponentiation mod n - the program

I discussed the logic for this program in a previous blog. Here is the logic converted into a program for the fx-50F:-

Lbl 0:?→X:?→A:?→B:While X≥B:X-B→X:WhileEnd:X→Y:2→C:1→D:
If C>A:Then X→D:Goto 2:IfEnd:Lbl 1:X²→X:While X≥B:X-B→X:
WhileEnd:2C→C:C≤A=>Goto 1:C÷2→C:A-C→A:DX→D:While D≥B:
D-B→D:WhileEnd:Y→X:2→C:C≤A=>Goto 1:A=1=>DY→D:While D≥B:
D-B→D:WhileEnd:Lbl 2:D▲Goto 0:

This program is 163 steps in length.

Exponentiation mod n - comments on the logic

In my previous post I presented some logic for obtaining the remainder when a number like 67¹¹ is divided by 41. I now want to go through how this logic works.

We are interested in dividing 67¹¹ by 41 and these positive integers are input and stored in X, A and B in the 2nd, 3rd and 4th lines of the logic. The first 'while' loop determines the remainder on dividing 67 by 41 and the result, 26, is stored in X. Essentially, 67 is reduced by 41 on each iteration until X is less than 41. A copy of this remainder (26) is kept in Y.

Memory C holds the current 'squared power'. Memory D is used to store the required calculated remainder and is initialised with 1.

If the input power (stored in A) was 1 rather than 11, then there is no more work to do, so we jump to label 2 and display the result.

The main process of calculating the required remainder by repeated squaring begins after label 1. In our example X currently contains 26 (the remainder on dividing 67 by 41). We square this and then the next 'while' loop obtains the remainder (20) on division by 41 and stores it in X. C is then doubled to 4 and as this is less than 11 we jump back to label 1. We keep on repeating this squaring until C reaches 16. As 16 is greater than 11 we determine that 67 has currently been raised to the power 8 (C divided by 2). We subtract 8 from 11 and store this 'residual' power (3) in A. The calculated remainder 'so far' (18 held in X) is multiplied with D (1) and the result stored in D. We store 26 back in X and set the 'squared power' in C back to 2. As 2 is less than the residual power 3 we begin again by going back to label 1.

Eventually the 'residual power' ends up being 1 in A and we have to take the contents of D and multiply this once more by 26 to get the remainder of 26¹¹ on division by 41. Note that if the power of 67 was even rather than odd, this last step isn't required.

The required remainder is in memory D and this is displayed. There is an option to return to the start of the logic again to enter a different set of numbers.

Exponentiation mod n - the logic

In a previous post I discussed how it is possible to use modular arithmetic to obtain information about the divisibility of a large number like 67¹¹. I showed that the problem of whether 41 divides this number can be reduced to a sequence of manageable chunks by using the method of repeated squaring modulo 41. I now give an example of the logic that can be used to solve this problem on a programmable calculator.

Label 0
Input X (67 in our example)
Input A (11 in our example)
Input B (41 in our example)
While X ≥ B
   Store X-B in X
WhileEnd
Store X in Y
Store 2 in C
Store 1 in D
If C>A then
   Store X in D
   Goto Label 2
EndIf
Label 1
Store X² in X
While X ≥ B
   Store X-B in X
WhileEnd
Store 2C in C
If C ≤A then
  Goto Label 1
EndIf
Store C/2 in C
Store A-C in A
Store DX in D
While D ≥ B
   Store D-B in D
WhileEnd
Store Y in X
Store 2 in C
If C ≤A then
   Goto Label 1
EndIf
If A=1 then
   Store DY in D
EndIf
While D ≥ B
   Store D-B in D
WhileEnd
Label 2
Display D
Goto Label 0

Exponentiation mod n

Sometimes it can be hard to obtain information about large numbers because of the complexity of multiplication and division. For example 67¹¹ is the 21 digit number 122130132904968017083 which can't be held accurately in a handheld calculator. If you wanted to determine whether 41 divided this number you would probably have to attempt this by long division. However, modular arithmetic offers a neat way round these problems.

Firstly we determine the remainder when 67 is divided by 41. We find that 67=1x41+26 and so the remainder is 26 and so we can write 67≡26 (mod 41). Now the neat trick of modular arithmetic is that the remainder on dividing 67¹¹ by 41 is the same as the remainder on dividing 26¹¹ by 41. However, rather than doing this in one go, we do it in bite-size chunks using repeated squaring to make the maths easier. So,  67²≡26² (mod 41) and since 26² is 676 and 676=16x41+20 then 67²≡20 (mod 41). Carrying on in a similar vein we have (67²)²=67⁴≡20² (mod 41) and as 20²=400=9x41+31 then 67⁴≡31 (mod 41). Further (67⁴)²=67⁸≡31² (mod 41) and as 31²=961=23x41+18 then 67⁸≡18 (mod 41).

Squaring any further doesn't help us as the index becomes 2x8=16 which is greater than 11. However as 67¹¹=67⁸x67³ we can continue by working out the remainder when 67³ is divided by 41 and multiplying this by the remainder when 67⁸ is divided by 41, which we have just worked out. Previously we saw that 67²≡20 (mod 41) and 67≡26 (mod 41) and so 67³=67²x67≡20x26 (mod 41). Now 20x26=520=12x41+28 and so 67³≡28 (mod 41). Hence 67¹¹≡18x28=504≡12 (mod 41) since 504=12x41+12.

Thus in answer to our original question 41 doesn't divide 122130132904968017083 as it leaves remainder 12.

This process of reducing a large division into a series of smaller steps using modular arithmetic lends itself well to computation on a programmable calculator. In particular, reducing the index by successive applications of repeated squaring is a fast way to obtain the remainder when a number can be expressed as a number raised to some power.