RSA for the HP-49

	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) jalarcon@uvigo.es

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':

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:

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:

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:

where 'Mi' is the chunk to get encripted and 'Ei' the encrypted result.
In order to decypher the following expression is applied:

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:

{ 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)

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).