🚀 go-pugleaf

In article <1992Sep28.202620.25342@linus.mitre.org> lewis@aera8700.mitre.org (Keith Lewis) writes:
>Find a pair of numbers, E and D, such that mod(E * D, (P-1)*(Q-1)) = 1
>You publish N and E as your public key.  To encrypt messages, calculate
>    Y = mod(X ** E, N), where X is the input data
>
>You keep N and D as your private key.  To decrypt messages, calculate
>    X = mod(Y ** D, N), where Y is the encrypted data
>
>If you have somebody's N and E, and you somehow factor N into P and Q, you
>must then find a D that works in the above equality (a non-trivial task, I
>think).  Then you can decrypt his/her messages.

Suppose you know P, Q, and E.  Then D is the multiplicative inverse of E
modulo (P-1)(Q-1).  Finding multiplicative inverses is in fact a trivial
operation if one keeps track of the quotients and remainders generated
while applying the Euclidean algorithm in GCD(E,(P-1)(Q-1)), but I'll
leave that as an exercise to the reader!

marshall
-- 
=========== 5 Joyce Lane, Woodbury, NY 11797, 516-364-9331,9379 ===========
============ PGP 2.0 Public Key available by finger or request ============
===== c/o Jack Gelfand,Psych Dept,Princeton U.,NJ 08544,609-258-2930 ======
= Original material(c) 1992, Marshall Flax <mgflax@phoenix.Princeton.EDU> =