Posted by: ardaayvaz | November 19, 2008

Reading Project: Groups, Factoring and Cryptography

Introduction

For my reading project, I chose to review the article called “Groups, Factoring and Cryptography” by A.R. Meijer. The article tackles a very interesting problem, cryptography, which we come across each day as we send and receive information over the Internet. In this article, we see that a very common cryptography process called RSA system can actually be understood by using some simple concepts we have learned in Math 152, such as the Euler’s totient function \phi(n)(the number of integers smaller than and coprime to n), modular arithmetic, and the order of elements in groups. RSA system uses public key cryptography, where the keys for encryption and decryption are independent from on another. What Meijer tries to do in this article is to give an overview of how the RSA system works, and then discusses ways to avoid possible attacks on this algorithm. Thus, the focus of the article is not to state new theorems, but rather to analyze the RSA system using more basic theorems of discrete math.

RSA System

The first assumption the author makes is that a good cryptographic system relies on big prime numbers, since the factorization of the multiplication of two large prime numbers would be computationally very hard to do, and therefore any system that would require the factorization of such number n will be safe.

So, n = p * q , where p and q are large prime numbers.

Since p and q are prime, we also know that \phi(n) = (p-1)(q-1) (comes from the fact that all numbers smaller than a prime p are coprime to p.)

Then, we choose an arbitrary number e, such that it is coprime to \phi(n).

We know from the class that for co-prime p and q, there exists integers a and b s.t. ap+bq=1. Using this result, we can conclude that there exists an integer d in RSA system s.t. de = 1 (mod \phi(n)).

From now on, we assume that the sender publishes e and n to public, and we have the encryption function:

E(m) = m^e (mod n) = x

and the decryption function:

D(x) = x^d (mod n)

We see that decryption works theoretically:

D(E(m)) = D(m^e (mod n))

= (m^e)^d (mod n)

= m^(1 + k*\phi(n)) (mod n) since e and \phi(n) are co-prime;

= m * m^(\phi(n)^k) (mod n)

= m * (1^k) (mod n) using the theorem that m^(\phi(n)) = 1

= m

An Example

Let me try to give an example of my own using relatively small numbers. Let’s say we choose n = 11*23 = 253, then \phi(n) = 220 and e = 13. This means d=17 using the Euler’s algorithm. If m = 2;

Then E(m) = E(34) = 2^13 (mod 253) = 96

Using D(96) = 96^17 (mod 253) = 2, so we get the same result back.

To recap, this system works, because the only easy way to figure out the order of an element of Z_n, is to know the factorization of n, since according to the Lagrange theorem, the order of an element of group G must divide the order of G. Therefore, we see that this theorem is simple, yet becomes very powerful in this system.

Attacking RSA

The second part of author’s argument is about how this system can be exploited. Since the encryption function is public, as well as the values of e and n, there is the danger that the hacker can re-apply the function to find our message.

So; for some integer k, E^k(m) can be equal to m and if this “k” is small, the hacker can reach to the message in few steps of iterating the function.

The theorem of the author is that, the order of e should be as high as possible in the group Z / \phi(n)

This mathematically means that m^(e^k) (mod n) = m for some k.

We also know that for an integer l, which is the order of e;

m^(e^l) (mod n) = m^(1+\phi(n)) (mod n) = m

Thus, we see that the hacking will work for an integer k, when k is the order of e in Z / \phi(n), and the number of repetitions will be small only if the order of e is small.

The other theory Meijer puts forth is that a high order of e is established when we choose n s.t \phi(\phi(n)) has very large prime factors. However, he doesn’t give a rigorous proof. He rather comes up with a practical way of choosing such n, and shows that it works in the RSA system to avoid exploitation of the system.

Conclusion

As a conclusion, I thought this article was quite interesting, since it brings the rather abstract concepts we have learned in class to an important real-life application. It also demonstrates how powerful those concepts can be when put into a computational context. Knowing the order of a group, or a certain element can give us a tremendous computational advantage, when we are working with data in real life, and this can be achieved through the theorems I mentioned such as Lagrange’s theorem. I suggest all of you to read it more closely to understand the mechanism behind RSA system, as well as the mentioned loophole in the system, and how to avoid it.

Advertisements

Responses

  1. I’m a high school math tacher in Michigan who happened across your blog project. Although most of your discussions move on a higher level than my students can follow, I have encouraged them to take a look at your posts for an glimpse into the broader world of what mathematicians are involved in. I often include some discussion of encryption when covering primes, so I thought I would use this RSA post as an opportunity to thank you for sharing your class with the rest of us. Good luck to you all and keep up the good work.

  2. Great! On behalf of the class, thank you for the encouragement! I’ve been very pleased with the posts we’ve had so far.

  3. A nice description of RSA. It’s an incredibly important theory in the modern world, and I’ve always found it stunning that something so simple can be so powerful. Mathematically, it could have been noticed hundreds of years ago, but perhaps our mindset changed with the modern concerns of security and information and computer algorithms, and that is what made the discovery possible. Real-world problems can sometimes influence even the most abstract mathematics in positive ways.

    I find the part about attacking RSA especially interesting.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: