[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RSA Questions
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 [email protected].
>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 [email protected].
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,