From: norm@netcom.com (Norman Hardy)
Date: Tue, 18 Jan 94 14:58:47 PST
To: cypherpunks@toad.com
Subject: Re: RSA Questions
Message-ID: <199401182256.OAA09505@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At  8:54 1/18/94 +0000, SuperDupont wrote:
>Hi Cypherpunks !
>
>I've got a few questions about the RSA encoding (if they're answered somewhere
>in litterature, just give directions, thanks)
>
>    If the public encryption key is e (the exponent) and n=p*q (the modulus),
>    then the encryption scheme is:
>
>                        cypher= (plain^e) mod n.
>
>    Number theory tells us that the reverse operation (taking the e-th root)
>    can be performed, as long as we know p and q: we know how to compute d
>    such that for any plain<n, (plain^e)^d=plain.
>
>    Now my questions are:
>
>        1. Is there a way to determine ALL the possible values of d verifying:
>        (plain^e)^d=plain for any plain<n (or at least have an evaluation for
>        their number) ?
>
>        In other words, is there a way to know the number of keys that unlock
>        what your public key locks ?
>
>        2. Is there a way to determine ALL the possible values of d verifying:
>        (plain^e)^d=plain for *a given plain* ?
>
>        In other words, is there a way to know the number of keys that unlock
>        *a given message* ?
>
>Here's an example that's quite worrying (maybe because I chose p and q
>to be random primes, and they have bad properties):
>
>e=17                    # Exponent
>p=967                   # Prime p
>q=1031                  # Prime q
>n=p*q=996977            # Public modulus
>
>phi=(p-1)*(q-1)=994980
>g=gcd(p-1,q-1)=2
>f=phi/g=497490
>d=(1/e) mod f=234113    # A possible value of d given by number theory
>
>Here's the result of the exhaustive search for the answer to question No. 2:
>
>plain=12345
>cipher=(plain^e) mod n
>decipher=(cipher^d) mod n
>
>The possible values for d (138 of them) are:
>
>3393 10603 17813 25023 32233 39443 46653 53863 61073 68283 75493 82703 89913
>97123 104333 111543 118753 125963 133173 140383 147593 154803 162013 169223
>176433 183643 190853 198063 205273 212483 219693 226903 234113 241323 248533
>255743 262953 270163 277373 284583 291793 299003 306213 313423 320633 327843
>335053 342263 349473 356683 363893 371103 378313 385523 392733 399943 407153
>414363 421573 428783 435993 443203 450413 457623 464833 472043 479253 486463
>493673 500883 508093 515303 522513 529723 536933 544143 551353 558563 565773
>572983 580193 587403 594613 601823 609033 616243 623453 630663 637873 645083
>652293 659503 666713 673923 681133 688343 695553 702763 709973 717183 724393
>731603 738813 746023 753233 760443 767653 774863 782073 789283 796493 803703
>810913 818123 825333 832543 839753 846963 854173 861383 868593 875803 883013
>890223 897433 904643 911853 919063 926273 933483 940693 947903 955113 962323
>969533 976743 983953 991163
>
>That makes a probability of 0.013%
>Looks to me like it's a LOT. Maybe I'm wrong.
>
>-zap
>
>-------------------------------------------------------------------------
>To find out more about the anon service, send mail to help@anon.penet.fi.
>Due to the double-blind, any mail replies to this message will be anonymized,
>and an anonymous id will be allocated automatically. You have been warned.
>Please report any problems, inappropriate use etc. to admin@anon.penet.fi.

Laudable Paranoia!
In short the numbers: cipher, decipher, plain, d and e must all be
relatively prime to p and q for all of this stuff to work. In practice,
since p and q are very large, the probability of the cryptanalyst finding
another value d that deciphers your message is about the same as him
finding p or q. That is the same probability of him factoring pq by
guessing. In your example 138 out of 996980 is about the probability of
being divisible by either p or q. You might check to make sure that the
message that you are enciphering is relatively prime to p and q. You could
better spend your, however, verifying that your hardware had not made a
mistake, which is more likely, unless, however you are sending one of your
factors so that a friend can share your secret key. In that case, however,
anyone with your public key can compute your secret key,