In the late 1970s a number of researchers realized that a public-key encryption scheme could be created using certain difficult mathematical problems. For example a few public key systems are based on the knapsack problem (see wikipedia.org/wiki/Knapsack_problem). A number of researchers came up with another scheme, based on the difficulty of factoring large numbers. Once such scheme that became very popular was invented by three mathematicians: Rivest, Shamar, and Adleman (A Method for Obtaining Digital Signatures and Public-key Systems, Comm. of the ACM, Feb. 1970, Vol. 21 no. 2, pp. 120-126).
Over the years RSA became refined to impove the protection offered. Eventually RSA obtained a patent on this method (which has since expired). Today this is the type of public key system used in PGP, GnuPG, SSH, SSL, and TLS (although others are used too).
RSA public key encryption can be understood by using a simple example. However note that in a real RSA system, the numbers used are much larger and need to satisfy other constraints to ensure maximum security.
The ASCII string"ABCD" = 1145258561 (as a 4 byte unsigned integer). However to keep the math simpler we will encrypt this as 4 numbers, Using a=1, B=2, C=3, etc., our message becomes this series of messages: 1 2 3 4.
n = p × q = 3 × 11 = 33(This is the step that is supposedly hard to reverse!)
φ(n) = (p-1) × (q-1) = 2 × 10 = 20
e × d mod φ(n) = 1
:
d = inv of e mod φ(n) = inv(7) mod 20 = 3
cyphertext = plaintext^{key} mod n = 1^{7} mod 33 = 1 mod 33 = 1 for 'A' = 2^{7} mod 33 = 128 mod 33 = 29 for 'B' = 3^{7} mod 33 = 2187 mod 33 = 9 for 'C' = 4^{7} mod 33 = 16384 mod 33 = 16 for 'D'The resulting cyphertext can be converted back to ASCII, say by adding "64" to each number (ASCII for 'A' = 65, 'B' = 66, ...).
plaintext = cyphertext^{key} mod n = 1^{3} mod 33 = 1 mod 33 = 1 for 'A' = 29^{3} mod 33 = 24389 mod 33 = 2 for 'B' = 9^{3} mod 33 = 729 mod 33 = 3 for 'C' = 16^{3} mod 33 = 4096 mod 33 = 4 for 'D'
A C program that demonstrates this can be found on Yborstudent,
in ~wpollock/bin/rsa
.
You can also view/download rsa.c source code.
Another version of RSA written in bc, "rsa.bc", can also be
found on Yborstudent, in ~wpollock/bin/rsa.bc
.
You can also view/download rsa.bc source code.