![]() |
Name: | RSA |
Plattform: | HP-49G | |
Description: | Simple implementation of the RSA encryption algorithm | |
Date: | October, 1999 | |
Size: | 1226 bytes | |
Author: | José Manuel Alarcón Aguín Mechanical Engineering E.T.S. Ingenieros Industriales Vigo (España) ![]() |
getting
started note:
This program is the HP-49G implementation of
the well-known RSA encryption/decryption algorithm. This implementation has
been written for educational purposses only, as explained later in this document.
This pack of programs is only intended for using on a HP-49G calculator or higher
so that it uses some functions especific to this machine. Anyway if any of the
programs detects another different machine it will stop telling you the motive.
In the same distribuiton of the program the commented source code is included
for a easier comprenhension.
Enjoy! and if you have some comments or suggestions please feel freee to contact
me at the e-mail above :-)
RSA
Encryption:
RSA is one of the most common used public key
algorithm and its valid for cyphering and to make digital signatures. Its name
came out from the initials of its inventors:Ron
Rivest, Adi Shamir y Leonard Adleman that define it on
1978.
Key
generation :
The first thing we have to do in order to put
the RSA to work is generate a couple of keys (one public and the other private)
that are needed to encrypt and decrypt the messages respectively. Both keys
are always sticked to a modulus that is needed to make some discrete maths operations.
Fist of all we ought to generate a par of prime numbers from which we'll obtain
the modulus for the encryption process. This two primes ('p' and 'q' for example)
should be choosen in a random fashion, and they must be as greater as possible
in order for the encryption to be hard to break. It's product 'm':
m = p x q
will act as the modulus in te encryption/decryption
process.
From this pair of numbers the public key 'C1' will be obtained too. this 'C1'
is also a random number and the only thing it must carry out is that it has
to be a relative prime of the product (p-1)
x (q-1).
Once the public key 'C1' is obtained the private one is directly obtained using:
C1 x C2 = 1 mod ((p-1) x (q-1))
thats 'C1' and 'C2' beeing inverse of each other in the ring of modulus (p-1) x (q-1).
At last, the public key is formed by 'C1' and
the modulus 'm', and the prvate key by 'C2' and 'm'.
In the RSA implementation I've done you can obtain these keys using the program
'GENKEYS' (the second label on the directory). After some seconds you will get
on the stack a pair of keys (piblic and private) and the correspondent modulus.
You must save them to a variable in order to use them later. We only must give
the public key and the modulus to the other people, keeping the private key
for our eyes only.
The third label on the RSA directory is named 'FAC', and it's
used to contain the "Key Size Factor". This factor takes control over
the size of the keys and modulus generated by 'GENKEYS'. The higher the value
in 'FAC' the greater the security of the encription. That doesn't mean that
we can put any number here. I've verified that values in 'FAC' greater than
10^11 lead to excessively high key generation process times. With this limit
value (10^11) we obtain quite reasonable process times, taking count, besides,
that RSA is designed most of all for encrypting small phrases and text in digital
signatures and even other private keys used in other asymetric encryption methods.
However, using 10^11 as a value for 'FAC' we can obtain modulus 'm' like, for
example:
5154228018862208512867
This number takes very long for the HP-49 to
factorize it (I get bored after half an hour waiting for it to end) and any
others generated with this value for 'FAC' will take more or less the same time
to get factorized.
That doesn't in absolute implicate that RSA for the HP-49 is a secure method
for sending very confidential messages, since anyone with patience and interest
enough can obtain the modulus 'm' factorization, and so 'p' and 'q', guessing
soon the public and private keys values. I've said before: This program is made
for educational purposses only although it can be used in a practical way sending
low importance messages.
The
encryption/dencryption process:
Once we have the keys, the message is divided
in blocks or chunks so that its numeric value is always less than the encryption
modulus 'm'. that means, in the HP-49 case, a big extra work and too big numbers
to manage, so I've adopted the easiest solution (although not good from the
theroretical point of view): simply divide the message in its correspondent
ASCII codes.
In order to get the message encypted, for each chunk of data (ASCII code in
the HP-49) is applied the expression:
Ei = Mi^C1 mod(m)
where 'Mi' is the chunk to get encripted and
'Ei' the encrypted result.
In order to decypher the following expression is applied:
Mi = Ei^C2 mod(m)
This is demonstrated in a quite long way that
I'm not going to write hera that bears the use of "Fermat's little theorem"
and the "Chinese remainder theorem".
Keys can be swaped in the encryption/dencription processes, for example in order
to use digital signatures. In the practice the public key uses to be the samallest
of them so that the encryption process or signature checking are very fast.
In a real application and perfectly programmed of RSA, the cyphered message
allways is a little bit larger than the clear text. That's because an extra
digit is always obtained in the cyphering process. Howecver this effect is of
low importance and doen't represent more than a little percentage of the size.
However in the current implementation I've done of the algorithm for the HP-49
this effect is really important. As I've done the chunks using the ASCII codes
directly, aeach of them gets much greater after beeing encrypted, so the encrypted
message is several times greater than the clear text, depending on the key size
(the 'FAC' value).
Example
of application:
Before anything else we must get assured that
we have the "Radians mode" set in the calculator. If no we must answer
"yes" when it ask it to us.
In order to encrypt the text "Secret Stuff!" with the public key 4264723
and a modulus of 40181463436921we must
put in the stack the following:
3: "Secret Stuff!"
2: 4264723
1: 40181463436921
and, after choosing 'RSA', we will get the list with the encrypted chunks:
{ 37789553811171 6897667489646 36892321337318 18010549703471 6897667489646 6993235818405 30383408828234 37789553811171 6993235818405 27290194209539 3839510730285 3839510730285 4982777788734 }
This is the list that we must pass along to whoever we want to communicate. This person, after receive the list, will decypher the message using it's private key, that in this case is 8337386909755 (as you can see it's larger than the public one), doing:
3: { 37789553811171 6897....}
2: 8337386909755
1: 40181463436921 (the
same modulus than the previous one)
getting the clear text on the stack.
If we wanted to use a digital signature we can put in a string, for example, our initials and the we will cypher them with our private key. After that we will send it to somebody with a message. This person will decypher our signature with our public key getting our initials. If the message were not sent by us it will get something unintelligible and he/she will know then that the message was not sent by us.
Licence:
This is FREEWARE software as long as you always distribute
all the files included here (the binary 'RSA.bin', the source code 'RSA.src'
the english readme 'readme.htm', the spanish readme 'leeme.htm' and the two
gif images).
© José Manuel Alarcón Aguín 1999