During the course of this year the Crypto Giants have been looking at the RSA Algorithm. They were required to make use of MATHEMATICA software in order to verify the mechanics of the RSA public key crypto system, that decryption of a message produces the original message. The project was supervised by Dr Gaza Maluleka. Below are 2 reports from their members, Ntombifuthi Khoza and Pilane Koma, in which they describe how they carried out the task.

 

CRYPTO GIANTS PROJECT

Verification of RSA Algorithm.

N Khoza

30 October 2015

Project Supervisor:Dr Gaza Maluleka

Contents

1 Historic Background on the

RSA Algorithm ………………………………………………………………………….. 3

2 Introduction …………………………………………………………………………….. 4

3 Task procedure …………………………………………………………………… 4

3.1 Prime numbers……………………………………………………………………………………………… 4

3.2 Computing n…………………………………………………………………………………………………… 4

3.3 Phi φ………………………………………………………………………………………………………………… 5

3.4 Public Key(e)………………………………………………………………………………………………….. 5

3.5 Private Key(d)……………………………………………………………………………………………….. 5

3.6 Encryption……………………………………………………………………………………………………… 5

3.7 Decryption……………………………………………………………………………………………………… 6

4 Conclusion …………………………………………………………………………………… 7

5 Reference ……………………………………………………………………………………… 8

 

1 Historic Background on the RSA

Algorithm

The RSA algorithm was developed by professor Ron River, Adi Shamir and Leonard Adlemen in 1977 at MIT. The algorithm is named RSA from the professors’ initials. The actual concept of public-key cryptography was discovered by Whiteld Diffie and Martin Hellman just one year earlier. Diffie and Hellman had devised a method that would allow the key of the cryptographic system to be known publicly but still have the system be a secure way to send messages. What they did not know was how to mathematically create one. RSA is an algorithm used by modern ICT devices to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys for encryption and decryption. This is also called public key cryptography, because one of the keys for encryption can be given to everyone.

The mathematics behind the RSA algorithm is simple, yet elegant. The algorithm works by exploiting concepts from number theory, including the properties of modular arithmetic and Fermats Little Theorem. RSA is, at its core, a piece of simple mathematics which makes use of facts and theorems from number theory, including Fermats Little Theorem. Public-key systems, like the RSA algorithm, are commonly used in transmission of secure data over e-mail and the internet. When you log into a site or make a purchase your passwords and credit card numbers are encrypted with either the RSA algorithm or an equivalent method that utilizes another one-way function. Methods like this are commonly used for small amounts of data. When transmitting large amounts of data, say gigabytes or terabytes of information, the use of RSA would be too slow for the average computer. So what is commonly done is the RSA algorithm is used to transfer a symmetric key for a faster encryption algorithm and the faster algorithm is used to encrypt and decrypt the large data set.

2             Introduction

This work is about verification of the mechanics of the RSA algorithm by choosing two large prime numbers p and q, public key and private key, then use them to encrypt and decrypt a word. The task is done using MATHEMATICA software

3             Task procedure

3.1            Prime numbers

A prime number is a number that is only divisible by 1 and its self only. Here we need two prime numbers p and q. To get those two prime numbers I used the function:

p=Prime[ 119 − 19]=55883811421 q=Prime[127 − 1] =691421363

The security of the RSA algorithm and messages encrypted using the algorithm relies on the difficulty of factoring the value of their product say n. If n could be easily factored into the corresponding values of p and q, then one could easily find the value of d(private key), hence it is essential to have p and q large enough

3.2            Computing n

n is the product of the two prime numbers in 3.1.

n=p∗q

=55883811421∗691421363

=38639261062342786823

3.3            Phi φ

We need to compute φ we will use it to get the greatest common divisor for e (public key) and φ (Phi) equals to 1.

φ = EulerPhi[n] = 38639261005767554040

3.4            Public Key(e)

In public-key cryptography, users reveal a public (encryption) key so that other users in the system are able to send private messages to them, but each user has their own private (decryption) key. The key to ensuring privacy in a public-key cryptosystem is for it to be extremely difficult to derive the decryption key from the publicly available encryption key.

Hence i choose e to be large so that it doesn’t compromise the security of the cipher,and e is chosen such that

GCD[e,φ] = 1 e = Prime[109 − 3] = 22801763459

I generated e like I did with p and q.

3.5            Private Key(d)

A private key is the decrypting key not known by anyone else but the user only because any one who knows the private key can read all you secret messages. The private key d is inverse of e(public key). Here I use the PomerMod funtion to get d the private key.

d = PowerMod[e, −1, Φ]

3.6            Encryption

Using parameters as defined from (3.1) to (3.5) we can encrypt messages but here I will encrypt my name, Ntombifuthi. For one to be able to encrypt any messages they have to convert it to be in ASCII codes so for me to get my name in ASCII codes I used the ToCharacterCode function in MATHEMATICA.

Converting Ntombifuthi to ASCII codes PT is the plaintext Ntombifuthi

PT=ToCharacterCode[”Ntombifuthi”]

= 78, 116, 111, 109, 98, 105, 102, 117, 116, 104, 10

Now i can encrypt the message.

CT is the ciphertext the encrypted message

CT=PowerMod[PT, e, n]

=14125653279241609279,19712818481001537754, 17136513747049505479,

7134303511394133014, 27972709429094498617, 7552654563436695202,

36560030266033587891, 21786391268662959683, 19712818481001537754,

23203449209605878169, 7552654563436695202

Ntombifuthi is encrypted to CT. Notice that this function has the public key e. If anyone reads the CT they wont know what it means so the message is safe from the public.

3.7            Decryption

Now an decrypting the ciphertext encrypted in (3.6) to get the plaintext using the function :

PT=PowerMod[CT, d, n]

=78, 116, 111, 109, 98, 105, 102, 117, 116, 104, 105

After decryptin the ciphertext we get PT equal to the plaintext in (3.6).

To return the ASCII codes to alphabets i use the function FromCahracterCode.

PT=FromCharacterCode[78, 116, 111, 109, 98, 105, 102, 117,

116, 104, 105]

=Ntombifuthi

The decryption is done and the reciever of the message can now read it.

4             Conclusion

In this work, I choose two distinct large prime numbers to compute the RSA modulus. I verified that encryption with a public key followed by decryption with a private key yields an original message. The RSA algorithm works because you can send secret message. The security is safe since is difficult to factor n to get p and q for you to get d the private you need to decrypt messages.

5             Reference

  • Niven, H. Zuckerman and H. Montgomery, An Introduction to The Theory of Numbers John Wiley and Sons, 1991 (5th edition).
  • Silverman, A Friendly Introduction to Number Theory, Prentice Hall (Upper Saddle River, NJ) 1997.
  • Diffie and M.E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22:644654, 1976.
  • Maluleka, RSA Report, 2006.

 

Crypto Giants Project

Verification of RSA Algorithm

Pilane Koma

Project Supervisor: Dr Gaza Maluleke

October 30, 2015

1           Intorduction

In cryptography we have two types of encryption, namely, symmetric key encryption and public key encryption. With the symmetric key encryption, the keys used for encryption and decryption are the same. In the public-key encryption schemes, the encryption key published for anyone to use and encrypt messages. However, only the receiving party has access to the key that decrypts the message. In this project I will be looking at a public-key encryption, RSA Algorithm. I will start off by giving a brief history of the cryptographic algorithm. Secondly, I will be reporting on the tasks that were given and lastly I will conclude on the mechanics of the RSA algorithm and why it works.

2           Brief History on the RSA Algorithm

Firstly, we need to recognise that the RSA algorithm is a public-private key cryptosystem. This helps us to better understand the system.

The idea of an asymmetric cryptosystem is attributed to Diffie and his partners Hellman and Merkle, who published the concept in 1975. Even though they published the concept they were not able to realize a one-way function that is hard to inverse. Over the course of a year two computer scientists, Ron Rivest and Adi Shamir, together with a mathematician, Leonard Adleman, made several attempts to the problem.

One evening, in April 1977 after they spent Passover at the house of a student, Rivest was unable to sleep, so he lay on his couch with a maths textbook. He began to pounder over the question that had been bugging him for a year: Is it possible to find a one-way function that can be reversed only if the receiver has some special information? He spent that evening formulating his idea and by the break of day, he had written a complete mathematical paper. The RSA algorithm is named after the three gentlemen and is now known as RSA.

3     Task

To complete the required task of verifying the RSA algorithm, I made use of MATHEMATICA. There are five tasks that need to be completed namely:

  • Finding ∅(n)
  • Choosing the public and private key
  • Converting the message M, my first name to decimal using ASCII
  • Encrypting M to get C
  • Decrypting C to get back M

3.1         Computing ∅(n)

First, I am going to start by choosing two distinct prime numbers p and q. I chose my p = 54363787

and q = 52027

I can test that these numbers are primes by executing the following command in MATHEMATICA:

PrimeQ[p]

followed by shift + enter, the command will either return a false or true. If it returns true then the number is a prime number, otherwise the number is not a prime numer.

Now that I have two distinct prime numbers, I compute n as follows:

n = p ∗ q

= 54363787 ∗ 52027

= 2828384746249

To compute ∅(n) I enter the following command into MATHEMATICA:

∅ = EulerPhi[n]

I execute the command to get:

∅(n) = 2828330330436

3.2         Choosing the private and public key

First I am going to choose the public key e. I choose the public key such that gcd(e,∅(n)) = 1. I have chosen the public key randomly and made use of MATHEMATICA to check that it meets the criteria. The public key that I chose is: e = 63218851849451 , and the command used in Mathematica is:

GCD[e,∅]

Now that I have the public key I can get the private key d such that ed = 1(mod∅(n)). Using MATHEMATICA, I enter the command:

d = PowerMod[e,−1,∅]

and in return I get that d = 1270486498631

Now I have the private and public keys and I can move over to the next task.

3.3         Converting my first name to decimal using the ASCII

My first name is PILANE. Using the ASCII, I will assign M to the decimal of my name such that:

M = 807376657869

M is what is known as the plaintext and I shall assign the value of M to PT in Mathematica.

3.4         Encrypting the message

When encryptng the message, M, I get what is known as the ciphertext and for the purposes of Mathematica I shall name it CT. To compute CT I enter the following command into MATHEMATICA:

CT = PowerMod[PT,e,n]

This command outputs the following result:

CT = 142039179996

and this is the encrypted message.

3.5         Decrypting the message

To decrypt the message we apply the inverse of the encryption and using MATHEMATICA we insert the following command:

PT = PowerMod[CT,d,n]

The end result is

PT = 807376657869

= M

Therefore, I get the original plaintext.

4           Conclusion

The RSA algorithm requires two main components which are p and q, which are required to be very large prime numbers. The reason for this is that, with the p and q being very large, then so will ∅n be very large. Now, even though we have computers and super computers that can compute very large numbers, the process of finding the prime numbers is not an easy job, even for a computer. If the numbers are large enough, even if the computer can find the numbers it would have found them after these numbers have been changed.

The RSA algorithm works because it requires that there to be two keys based on prime numbers. Encryption and decryption keys are inverses of each other. I showed that encrypting a message followed by decrypting the encrypted message yields an original message. Prime numbers are unique and very difficult to find especially by humans.

References

  • wikipedia.com
  • Silvia Robles, The RSA Cryptosystem, 2006
  • Michael Calderbank, The RSA Cryptosystem: History, Algorithm, Primes, August 20, 2007
  • Gaza Maluleke, RSA Report, 2006

 

 

How clear is this post?