Help with RSA algorithm?

RSA starts with two (large) primes, p and q, and a number, e, relatively prime to the product (p-1)(q-1). Using Euclid's algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm ), it is easy to compute a number "d" such that the product (ed)≡1 mod(p-1)(q-1).

The code-maker publishes the pair (pq, e). Anyone with a message, M<(pq), to encode merely computes C=M^e mod(pq). The code-maker can decode the coded message, C, by computing C^d mod(pq). The fact that this equals M is a simplified version of Euler's Theorem (http://en.wikipedia.org/wiki/Euler%27s_theorem ):

     n ≡ 1   mod (p-1)(q-1)   ⇒   Mⁿ ≡ M   mod (pq),

Why is this a useful thing to do? It turns out that computing "d" is equivalent to factoring (pq), which, to date, has proven very difficult (if p & q are very large and random). Here are some recent records: http://www.crypto-world.com/FactorRecords.html (The factoring is not impossible. It just requires thousands of computers and years of time.) Note that the code-maker publishes the product, but not the factors!

So the first part of your assignment just requires you to compute:

     9³ mod (3×11)   { =MOD(9^3,3*11) on a spreadsheet}

Then find a number "d" so that:   de ≡ 1 mod (3-1)(11-1)

which should be simple. Add "1" to multiples of (3-1)(11-1) until you find a number divisible by e=3. Or use the full Euclidean algorithm.

Finally decode the message from the first calculation by raising the coded message to the power of that "d". The result, mod(33), will be 9, unless you have made an arithmetic mistake!

-------

Signatures are a backwards process. The code-maker takes as message M and uses the decoding exponent, d, to compute the signature: S=M^d mod(pq). Anyone can now calculate S^e=M mod(pq) to verify the signature, but only the code-maker (or someone who has cracked the code) could have created that signature. In your example, the signature is:

     S = 2^17 mod (3×11)   { =MOD(2^17,3*11) on a spreadsheet}

Verify it by computing:

     S^13 mod (3×11)   { =MOD(S^13,3*11) on a spreadsheet}

Of course the answer will be "2".

Hi all encryption is changing one value for another but you must use the same key to decrypt to get the original text or quantity. substitution is all the encryption is.