Given an [[wp:RSA|RSA]] key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings.

'''Background'''

RSA code is used to encode secret messages. It is named after Ron Rivest, Adi Shamir, and Leonard Adleman who published it at MIT in 1977. The advantage of this type of encryption is that you can distribute the number “<math>n</math>” and “<math>e</math>” (which makes up the Public Key used for encryption) to everyone. The Private Key used for decryption “<math>d</math>” is kept secret, so that only the recipient can read the encrypted plaintext.

The process by which this is done is that a message, for example “Hello World” is encoded as numbers (This could be encoding as ASCII or as a subset of characters <math>a=01,b=02,...,z=26</math>). This yields a string of numbers, generally referred to as "numerical plaintext", “<math>P</math>”. For example, “Hello World” encoded with a=1,...,z=26 by hundreds would yield <math>0805 1212 1523 1518 1204</math>.

The plaintext must also be split into blocks so that the numerical plaintext is smaller than <math>n</math> otherwise the decryption will fail.

The ciphertext, <math>C</math>, is then computed by taking each block of <math>P</math>, and computing
: <math>C \equiv  P^e \mod n</math>
Similarly, to decode, one computes
: <math>P \equiv  C^d \mod n</math>

To generate a key, one finds 2 (ideally large) primes <math>p</math> and <math>q</math>. the value “<math>n</math>” is simply: <math>n = p \times q</math>.
One must then choose an “<math>e</math>” such that <math>\gcd(e, (p-1)\times(q-1) ) = 1</math>. That is to say, <math>e</math> and <math>(p-1)\times(q-1)</math> are relatively prime to each other.

The decryption value <math>d</math> is then found by solving
: <math>d\times e \equiv  1 \mod (p-1)\times(q-1)</math>

The security of the code is based on the secrecy of the Private Key (decryption exponent) “<math>d</math>” and the difficulty in factoring “<math>n</math>”.  Research into RSA facilitated advances in factoring and a number of [http://www.rsa.com/rsalabs/node.asp?id=2092 factoring challenges].   Keys of 768 bits have been successfully factored.  While factoring of keys of 1024 bits has not been demonstrated, NIST expected them to be factorable by 2010 and now recommends 2048 bit keys going forward (see [[wp:Key_size#Asymmetric_algorithm_key_lengths|Asymmetric algorithm key lengths]] or [http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf NIST 800-57 Pt 1 Revised Table 4: Recommended algorithms and minimum key sizes]).

'''Summary of the task requirements:'''

*  Encrypt and Decrypt a short message or two using RSA with a demonstration key.
*  Implement RSA do not call a library.
*  Encode and decode the message using any reversible method of your choice (ASCII or a=1,..,z=26 are equally fine).
*  Either support blocking or give an error if the message would require blocking)
*  Demonstrate that your solution could support real keys by using a non-trivial key that requires large integer support (built-in or libraries).  There is no need to include library code but it must be referenced unless it is built into the language. The following keys will be meet this requirement;however, they are NOT long enough to be considered secure:
:: n = 9516311845790656153499716760847001433441357
:: e = 65537
:: d = 5617843187844953170308463622230283376298685
*  Messages can be hard-coded into the program, there is no need for elaborate input coding.
*  Demonstrate that your implementation works by showing plaintext, intermediate results, encrypted text, and decrypted text.

{{alertbox|#ffff70|'''<big>Warning</big>'''<br/>Rosetta Code is '''not''' a place you should rely on for examples of code in critical roles, including security.<br/>Cryptographic routines should be validated before being used.<br/>For a discussion of limitations and please refer to [[Talk:RSA_code#Difference_from_practical_cryptographical_version]].}}