INTRODUCTION
"In cryptography, RSA is an algorithm for public key encryption. It was the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys." However, within recent years, various strengths of the RSA cipher have been successfully broken as a result of advancements in methods of factoring large primes and increasing computer processing power.
THE PROJECT
During the course of the two weeks, students will be introduced to the fundamental concepts of encryption along with becoming knowledgeable about the workings of the RSA cipher specifically. As time is a limiting factor, experimenting with a long key would be unfeasible. However, using a less complex key, students will reproduce experiments similar to those done by RSA researchers. The project will be built upon their knowledge of RSA encryption. It will challenge them to not only write an application capable of generating keys, encrypting and decrypting, and factoring a RSA prime, but time permitting, it will also involve parallel code writing using MPI for benchmarking in a cluster environment.
Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but you can also use OpenSSL to generate and examine a real keypair.
| p = 61 | — first prime number (to be kept secret or deleted securely) |
| q = 53 | — second prime number (to be kept secret or deleted securely) |
| n = pq = 3233 | — modulus (to be made public) |
| e = 17 | — public exponent (to be made public) |
| d = 2753 | — private exponent (to be kept secret) |
The public key is (e, n). The private key is d. The encryption function is:
encrypt(m) = me mod n = m17 mod 3233
where m is the plaintext. The decryption function is:
decrypt(c) = cd mod n = c2753 mod 3233
where c is the ciphertext.
To encrypt the plaintext value 123, we calculate
encrypt(123) = 12317 mod 3233 = 855
To decrypt the ciphertext value 855, we calculate
decrypt(855) = 8552753 mod 3233 = 123
For additional formulas and background information please see Wikipedia’s RSA page.
ANIMATIONS
SI 2006
SI 2005
Jonathan Mudronja is the group leader for the Cryptanalysis project. His office is in OSC, cubicle 420-27, phone 292-6066.
For assistance, write si-contact@osc.edu or call 614-292-0890.
