Browse Prior Art Database

On the Solution of a Certain Congruence Related to the RSA Public Key Cryptosystem

IP.com Disclosure Number: IPCOM000108097D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 8 page(s) / 313K

Publishing Venue

IBM

Related People

Martino, MJ: AUTHOR

Abstract

In the RSA Public Key Cryptosystem, knowledge by an opponent of the secretly held phi(m) (sometimes called Euler's totient function), allows computation of the secretly held decryption key, d. This is accomplished by using the publicly known encryption key, e, and the congruence that relates the two keys, namely, e * d == 1 (mod phi (m)). If the actual phi (m) can be guaranteed to be a member of the set which has a limited number of members, it may be possible to identify the secretly held deciphering key by search. This article describes an algorithm that can reduce the set of trial totients and, hence, the set of trial deciphering keys, The method is to search for solutions to the congruence (n ** x) == 1 (mod m), since every solution is either a divisor of phi (m) or has a factor in common with phi (m).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 21% of the total text.

On the Solution of a Certain Congruence Related to the RSA Public Key Cryptosystem

       In the RSA Public Key Cryptosystem, knowledge by an
opponent of the secretly held phi(m) (sometimes called Euler's
totient function), allows computation of the secretly held decryption
key, d.  This is accomplished by using the publicly known encryption
key, e, and the congruence that relates the two keys, namely, e * d
== 1 (mod phi (m)).  If the actual phi (m) can be guaranteed to be
a member of the set which has a limited number of members, it may be
possible to identify the secretly held deciphering key by search.
This article describes an algorithm that can reduce the set of trial
totients and, hence, the set of trial deciphering keys,  The method
is to search for solutions to the congruence (n ** x) == 1 (mod m),
since every solution is either a divisor of phi (m) or has a factor
in common with phi (m).  In particular, it is computationally
superior in all reasonable situations to a direct search.
RSA Cryptosystem Operational Overview

      This is a brief overview of the RSA Public Key Cryptosystem.
The RSA description here is taken from the original paper, published
in (1).  See the Appendix for the notation used in this report.

      To Encipher:
      1.  Convert plaintext to numbers using a convenient table.
      2.  Divide the digit stream into groups of fixed length,
a(1)...g(n).
      3.  Raise each group to the power of the public key, e, modulo
the public modulus, m.
                 (g(j) ** e) == h(j) (mod m)

      To Decipher:
      1.  Divide the digit stream h(1)...h(n) into fixed length
groups.
      2.  Raise each group to the power of the secret key, d, modulo
the public modulus, m.
                 (h(j) ** d) == g(j) (mod m)
      3.  Convert the residue to plaintext using the enciphering
table.
      Example:
      Let m = 2773, e = 17, d = 157, and phi(m) = 2668. Let
the table be:  blank = 00, a = 01, b = 02, etc.
      Then, IT'S ALL GREEK -> 0920 1900 0112 1200 0718 0505 110
      And, (0920 ** 17) == 948 (mod 2773) for a cipher stream:
            0948 2342 1084 1444 2663 2390 0778

      The reader can verify that the cipher stream blocks, when
raised to the power of the decryption key (d = 157) will yield the
original plaintext.
RSA Cryptosystem Internals Overview

      The particular values used for e, d, p and q in the RSA are
not arbitrary.  In fact, they must be very carefully chosen as there
are a number of restrictions, some better known than others, that
affect the security of the system. See, for example, (2,3).  This
article assumes that these constraints are known to the user and the
specific numbers chosen satisfy those constraints.

      The public modulus, m, is the product of two primes, p and q.
That is,
           m= p * q.

      The "phi function" is...