[SOLVED] 1024-bit asymmetric RSA encryption

[dcparham]

http://etutorials.org/Programming/Programming+.net+security/Part+III+.NET+Cryptography/Chapter+15.+Asymmetric+Encryption/15.1+Asymmetric+Encryption+Explained/ - explains 4 steps to creating Public Keys for encryption.  step 3 involves d=d^-1 mod (p-1)(q-1P, where their sample data lead to d=19^1 mod(660) = 139.  i do not get 139.  instead 19^-1 = .05623, then [.05623]mod[660]=.05623, possibly another small number due to such small numbers being multiplied together.  can someone help me with the encryption algorithm?  here're steps 1-4 from the above referenced site:

 

[1]Choose two large random prime numbers, p and q, of equal length and multiply them together to create n, the RSA key modulus.

Select p as 23 and q as 31, so that the modulus, n, is: n = p x q = 23 x 31 = 713.

 

[2]Randomly choose e, the public exponent, so that e and (p - 1)(q - 1) are relatively prime.

Numbers are "relatively" prime when they share no common factors except 1. For these test values  select a value for e that has no common factors with 660. Select e as 19.

 

*[3]Compute the private exponent, d, where d = e-1mod((p - 1)(q - 1)).

For our example, we calculate d as follows: d = 19-1mod(22 x 30) = 139.

 

[4]The public key consists of e and n. The private key is d. Discard p and q, but do not reveal their values.

 

thank you!!

 

[btherl]

RSA deals with modular arithmetic, so the standard functions aren't useful.  The meaning of "power of -1" is also different, as here it refers to an inverse in modular arithmetic, rather than an inverse in real arithmetic.

 

Consider that in real arithmetic, a^-1 is the number such that a * a^-1 = 1.  This is easy to find in real arithmetic, as it's just 1/a, giving a * 1/a = 1.

 

But in modular arithmetic, it's much more difficult to calculate.  What you want is the integer b such that a * b (mod n) = 1.  For example, the inverse of 2 in mod 5 arithmetic is 3, because 2 * 3 (mod 5) = 6 (mod 5) = 1.

 

Anyway, the place to start if you want to implement RSA is learning modular arithmetic.

[btherl]

See also this reference: http://mathworld.wolfram.com/ModularInverse.html

 

which has this fact, important for RSA:

 

"Every nonzero integer b has an inverse (modulo p) for p a prime and b not a multiple of p. For example, the modular inverses of 1, 2, 3, and 4 (mod 5) are 1, 3, 2, and 4."

 

It turns out that p doesn't necessarily have to be prime, there are other conditions that are close enough to make things work.

[dcparham]

thank you for rectifying my approach!  to borrow from an old Southern metaphor:  i will stop "barking up the wrong tree, and bark up the correct one"

[dcparham]

solved enough to get going in the right direction.