## RCM3720 Cryptography, Network and Computer Security

### Laboratory Class 5: RSA and public-key cryptosystems

• You can leave the ")quiet" off if you like. The file is also available here. If you obtain it from the website, save it to a place of your choice, and read it into your Axiom session using the full path, as shown above.
• Now create some large primes and their product:
• r() == rand(2^100)
• p:=nextPrime(r())
• q:=nextPrime(r())
• n:=p*q
• Choose a value e and ensure that it is relatively prime to your (p-1)(q-1), and determine d=e^-1 mod (p-1)(q-1). (Use the invmod function here).
• Create a plaintext:
• pl:="This is my plaintext."
• (or any plaintext you like), and convert it to a number using the str2num procedure from the file above:
• pln:=str2num(pl)
• Encrypt this number using the RSA method:
• ct:=powmod(pln,e,n)
• and decrypt the result:
• decrypt:=powmod(ct,d,n)
• num2str(decrypt)
• With a friend, swap your public keys and use them to send each other a ciphertext encrypted with your friend's public key.
• Now decrypt the ciphertext you have received using your private key.
• Now try Rabin: create two large primes p and q and ensure that each is equal to 3 mod 4. (You might have to run the nextPrime command a few times until you get primes which work.)
• Create N=pq and create a plaintext pl, and its numerical equivalent.
• Determine the ciphertext c by squaring your number mod N.
• Determine the s and t for which sp+tq=1 by using the extendedEuclidean function.
• Now follow through the Rabin decryption:
• cp:=powmod(c,(p+1)/4,N)
• cq:=powmod(c,(q+1)/4,N)
• c1:=(s*p*cq+t*q*cp)::ZMOD N,num2str(c1::INT)
• c2:=(s*p*cq-t*q*cp)::ZMOD N,num2str(c2::INT)
• c3:=(-s*p*cq-t*q*cp)::ZMOD N,num2str(c3::INT)
• c4:=(-s*p*cq+t*q*cp)::ZMOD N,num2str(c4::INT)
• One of the outputs c1, c2, c3 and c4 should produce the correct plaintext; the others should be gibberish.
• As above, swap public keys with a friend, and use those public keys to encrypt a message to him or her. Now decrypt the ciphertext you have been given.
• For the el Gamal system, you need a large prime and a primitive root. Create a large prime p and find a primitive root a using.
• a:=primitiveElement()\$PF p
• The primitiveElement command is not very efficient, so if it seems to be taking a long time, abort the computation and try with another prime.
• Do this in pairs with a friend, so that you each agree on a large prime and a primitive root.
• Now choose a random value A:
• A:=random(p-1)
• and create your public key A1=a^A (mod p):
• A1:=a^A
• Swap public keys with your friend.
• Create a plaintext pl and its number pln, and create the ciphertext as follows (where A1 is your friend's public key):
• k:=random(p-1)
• K:=A1^k
• C:=[a^k, K*pln]
• This pair C is the ciphertext you send to your friend.
• Now decrypt the ciphertext you have been sent:
• K:=C.1 ^ A
• m:=C.2/K
• num2str(m::INT)