[wrong][spam] Cracking PGP

Karl gmkarl at gmail.com
Fri Jun 18 11:51:04 PDT 2021


Here are further words from Wikipedia, to learn against later.
https://en.m.wikipedia.org/wiki/RSA_(cryptosystem)

In the original RSA paper,[2]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-rsa-2>
 the Euler totient function
<https://en.m.wikipedia.org/wiki/Euler_totient_function> *φ*(*n*) = (*p* −
1)(*q* − 1) is used instead of *λ*(*n*) for calculating the private
exponent *d*. Since *φ*(*n*) is always divisible by *λ*(*n*) the algorithm
works as well. That the Euler totient function
<https://en.m.wikipedia.org/wiki/Euler_totient_function> can be used can
also be seen as a consequence of Lagrange's theorem
<https://en.m.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29>
applied
to the multiplicative group of integers modulo pq
<https://en.m.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n>.
Thus any *d* satisfying *d*⋅*e* ≡ 1 (mod *φ*(*n*)) also satisfies *d*⋅*e* ≡
1 (mod *λ*(*n*)). However, computing *d* modulo *φ*(*n*) will sometimes
yield a result that is larger than necessary (i.e. *d* > *λ*(*n*)). Most of
the implementations of RSA will accept exponents generated using either
method (if they use the private exponent *d* at all, rather than using the
optimized decryption method based on the Chinese remainder theorem
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#Using_the_Chinese_remainder_algorithm>
described
below), but some standards such as FIPS 186-4
<http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=62> may
require that *d* < *λ*(*n*). Any "oversized" private exponents not meeting
that criterion may always be reduced modulo *λ*(*n*) to obtain a smaller
equivalent exponent.

Since any common factors of (*p* − 1) and (*q* − 1) are present in the
factorisation of *n* − 1 = *pq* − 1 = (*p* − 1)(*q* − 1) + (*p* − 1) + (*q* −
1),[17]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-17> it is
recommended that (*p* − 1) and (*q* − 1) have only very small common
factors, if any besides the necessary 2.[2]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-rsa-2>[18]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-18>[19]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-19>[20]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-20>

Note: The authors of the original RSA paper carry out the key generation by
choosing *d* and then computing *e* as the modular multiplicative inverse
<https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse> of *d*
 modulo *φ*(*n*), whereas most current implementations of RSA, such as
those following PKCS#1 <https://en.m.wikipedia.org/wiki/PKCS1>, do the
reverse (choose *e* and compute *d*). Since the chosen key can be small
whereas the computed key normally is not, the RSA paper's algorithm
optimizes decryption compared to encryption, while the modern algorithm
optimizes encryption instead.[2]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-rsa-2>[21]
<https://en.m.wikipedia.org/wiki/RSA_%28cryptosystem%29#cite_note-21>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 20848 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20210618/cf944439/attachment.txt>


More information about the cypherpunks mailing list