From: an56238@anon.penet.fi (SuperDupont)
Date: Tue, 18 Jan 94 01:38:38 PST
To: cypherpunks@toad.com
Subject: RSA Questions
Message-ID: <9401180854.AA08208@anon.penet.fi>
MIME-Version: 1.0
Content-Type: text/plain



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.