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,