RCM3720 Cryptography, Network and Computer Security
Laboratory Class 5: RSA and public-key cryptosystems
- Read in this file:
-
)read "S:/Samples/RCM3720/rcm3720.input" )quiet
- 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:
- Encrypt this number using the RSA method:
- 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:
- and create your public key A1=a^A (mod p):
- 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)