CSC $241$

Programming Assignmnet #$5$

Spring'$24$

RSA Public$-$Key Cryptosystem

Overview. Write a program to implement the RSA public$-$key cryptosystem. The RSA $($RivestShamir$-$Adleman$)$ cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate huge integers $($hundreds of digits$).$ The built$-$in C$/$Java type int is only capable of dealing with $16$ or $32$ bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers, using Biginteger in Java or simply using Python. You will use this data type to write a client program that encrypts and decrypts messages using RSA.

Note: the training wheels are off on this assignment $-$ you're starting with a blank screen, not our code. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in$.$ Remember to thoroughly test and debug each function as you write it$.$

The RSA cryptosystem. The RSA public key cryptosystem involves three integer parameters $d,e,$ and $n$ that satisfy certain mathematical properties. The private key $(d,n)$ is known only by Bob, while the public key $(e,n)$ is published on the Internet. If Alice wants to send Bob a message $($e$.$g$.,$ her credit card number$)$ she encodes her message as an integer $M$ that is between $0$ and $n-1.$ Then she computes:

$E(M)=$Mmodn

and sends the integer $E(M)$ to Bob. As an example, if $M=2003,e=7,d=2563,n=3713,$ then Alice computes

$E(M)={2003}^{TT}$mod$3713=129,350,063,142,700,422,208,187$mod$3713=746.$

When Bob receives the encrypted communication $E(M),$ he decrypts it by computing:

$M=E(M{)}^d$modn.

Continuing with the example above, Bob recovers the original message by computing:

$M={746}^{2803}$mod$3713=2003.$

To check your arithmetic, you may use Maclab, maple.

Part $2($encryption and decryption$).$ Now it's time to put all your hard work to use. The encryption and decryption processes are identical, except that they involve different encryption$/$decryption keys. Write a program rsa.java that takes in one command line arguments $($the name of the encryption key$),$ reads in a decimal string from standard input, and applies the RSA function to the message. It should work as follows. In real applications, you might want to send an ASCII text message instead of a decimal integer; however, you are only responsible for handling decimal inputs.

RSA function. The key step is to implement the RSA function $($a$.$k$.$a$.$ modular exponentiation$)$: given three extended precision integers $a($the base$),b($the exponent$),$ and $n($the modulus$),$ compute $c=a^b$modn. You will implement this as the function XPrsa$()$ in xp$.$c$.$

A natural way to compute $c$ is to set $x=1$; then multiply it by $a,b$ times; then set $c=$xmodn. This method suffers from two serious performance bugs.

First, observe that if the inputs $a,b,$ and $n$ are N$-$digit decimal integers, then the intermediate result $x$ could contain as many as ${10}^N$ digits. To see the great importance of this, observe that if $N$ is $30,$ the intermediate result could consume a terrabyte of memory!

The second problem is that repeating anything $b$ times will be slow. If $b$ is even moderately large $($say $30$ decimal digits$),$ it will take centuries to execute, even on the fastest supercomputer. Data structure