Monday, 28 April 2014
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 25013 (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133133 (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.
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 25013 (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133133 (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.
Sunday, 27 April 2014
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)=(p1-1)(p2-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 113≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡1213(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')133 (mod 221) which again you can use the Exponentiation mod n program to do.
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)=(p1-1)(p2-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 113≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡1213(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')133 (mod 221) which again you can use the Exponentiation mod n program to do.
Saturday, 26 April 2014
RSA Encryption
Having written these four programs for the fx-50F:-
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 p1 and p2 are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p1p2=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.
This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p1 and p2 (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.
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 p1 and p2 are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p1p2=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.
- Choose two prime numbers p1 and p2
- Calculate n=p1p2 and φ(n)=(p1-1)(p2-1)
- Choose a positive integer encryption exponent e such that e is less than φ(n) and the gcd(e,φ(n))=1
- Calculate the decryption exponent d which is the inverse of e modulo φ(n), that is ed≡1 (mod φ(n))
- To encrypt a positive integer message m calculate m' where m'≡me (mod n)
- To decrypt message m' calculate m≡(m')d (mod n)
This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p1 and p2 (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.
Thursday, 24 April 2014
Exponentiation mod n - execution of the program
In my previous post I detailed a program for finding remainders when a number like 6711 is divided by 41. In my first post I showed that 6711 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 6711 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 67617 is the 1,127 digit number (from WolframAlpha)
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 67617mod 10).
If we didn't know what the number 6711 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 67617 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 67617mod 10).
Wednesday, 23 April 2014
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.
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.
Tuesday, 22 April 2014
Exponentiation mod n - comments on the logic
In my previous post I presented some logic for obtaining the remainder when a number like 6711 is divided by 41. I now want to go through how this logic works.
We are interested in dividing 6711 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 2611 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.
We are interested in dividing 6711 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 2611 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.
Subscribe to:
Posts (Atom)