Mathimagics

If you have a question about RSA, please send me a PM and I'll update this thread with a reply
[horizontalrule]x[/horizontalrule]How does RSA work?[horizontalrule]x[/horizontalrule]I don't intend to rewrite the large amount of information already published on this subject, most of which was written by people far more qualified than myself.

However, here are some useful links:

http://world.std.com/~franl/crypto/rsa-guts.html (A one-page summary of the formula)

http://www.xtremevbtalk.com/t31778.html (BillSoo's "Simple Encryption" tutorial includes a simple example of the RSA formula in action)

http://en.wikipedia.org/wiki/RSA(The Wikipedia base page for RSA, very useful and readable introduction)

http://www.cacr.math.uwaterloo.ca/hac/ (The University of Waterloo's "Handbook of Applied Cryptography", a comprehensive textbook of cryptography methods, algorithms and implementation techniques. Individual chapters can be downloaded as PS or PDF files. Chapter 8 "Public Key Encryption", focuses on RSA in detail)

[horizontalrule]x[/horizontalrule]Why does RSA require "large primes"?[horizontalrule]x[/horizontalrule]RSA involves 3 key components, the modulus M, the encryption key E, and the decryption key D

Both M and E are made public, D is kept private.

The system requires that M is the product of 2 primes, P and Q. It further requires that E be chosen so that it has no common factors with the product (P-1)x(Q-1). This is usually written as "E, P-1 and Q-1 are relatively prime".

P and Q have to be primes in order to ensure that the simple encryption function C = T ^ E mod M is guaranteed to be one-to-one. That is, for any plaintext value T, we want the function to produce a unique cyphertext value C.

While E can be chosen from many, many candidates, D, the private key, is then "fixed", it must be the multiplicative inverse of E. This simply means that D x E = 1 mod (P-1)(Q-1).

This then creates an invertible function, so that T = C ^ D mod M.

If I know the values of P, Q and E, computing D is a breeze, and there is no security.

But the values made public are E and M. I don't know which P and Q were multiplied to give M.

To break the code, I therefore need to factorise M.

And this is the basis of the RSA system's security, because if P and Q are large enough, it can take years, millennia, or even eons to factorise it, because, although there are simple algorithms for factorising numbers, the time required for their execution (their algorithmic complexity) is proportional to the size of the factors.

The factorisation problem is one of the fundamental problems considered in what's called "complexity theory".


[horizontalrule]x[/horizontalrule]Could I break the code without factorising M?[horizontalrule]x[/horizontalrule]Given a cyphertext value C, and the encryption keys E and M, are there ways to find T such that T ^ E = C mod M without factorising M?

This is called the "RSA problem", and Complexity Theory suggests that, while various algorithms have been formulated, they actually have similar (or worse) algorithmic complexity to that of the factorisation problem.