From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Wed, 19 Jan 94 20:14:06 PST
To: cypherpunks@toad.com
Subject: RSA: questions
Message-ID: <9401200412.AA03180@flammulated.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

>I'm willing to believe you. Any general formulas giving the
>probability of solutions for the d's ? Maybe I'm asking the wrong
>question. I'll ask again.

>What are the properties of those d that unlock ALL messages encrypted
>by e What are the properties of those d that unlock a GIVEN message
>encrypted by e

I beleive if p and q are well chosen (p-1 and q-1 have large prime
factors, for example p = 2p'+1 and q=2q'+1 with p' and q' prime) then
only two values of d will work as the decryption exponent.  This makes
guessing d as "easy" as guessing either p or q in the first place.

For example: p = 11 (p' = 5), q = 23 (q' = 11), n = 253, phi(n) = 220

I picked e = 7, gcd(e,n) = 1, solve for d = 63

The message 20 encrypts to 20^7  mod 253 = 136

I make a brute force search for d by raising C to all possible values
of d, from 1 to 253, looking for what decrypts to the original message.

Only two values work: d = 63 (what I got above) and d = 173.  There
are as many useful d's as there are factors in n; clearly for large
values of p and q guessing d is as infeasible as guessing p or q.

Karl L. Barrus
klbarrus@owlnet.rice.edu

d 136^d mod 253
- ---------------
1 136		2 27		3 130		4 223
5 221		6 202		7 148		8 141
9 201		10 12		11 114		12 71
13 42		14 146		15 122		16 147
17 5		18 174		19 135		20 144
21 103		22 93		23 251		24 234
25 199		26 246		27 60		28 64
29 102		30 210		31 224		32 104
33 229		34 25		35 111		36 169
37 214		38 9		39 212		40 243
41 158		42 236		43 218		44 47
45 67		46 4		47 38		48 108
49 14		50 133		51 125		52 49
53 86		54 58		55 45		56 48
57 203		58 31		59 168		60 78
61 235		62 82		63 20		64 190
65 34		66 70		67 159		68 119
69 245		70 177		71 37		72 225
73 240		74 3		75 155		76 81
77 137		78 163		79 157		80 100
81 191		82 170		83 97		84 36
85 89		86 213		87 126		88 185
89 113		90 188		91 15		92 16
93 152		94 179		95 56		96 26
97 247		98 196		99 91		100 232
101 180		102 192		103 53		104 124
105 166		106 59		107 181		108 75
109 80		110 1		111 136		112 27
113 130		114 223		115 221		116 202
117 148		118 141		119 201		120 12
121 114		122 71		123 42		124 146
125 122		126 147		127 5		128 174
129 135		130 144		131 103		132 93
133 251		134 234		135 199		136 246
137 60		138 64		139 102		140 210
141 224		142 104		143 229		144 25
145 111		146 169		147 214		148 9
149 212		150 243		151 158		152 236
153 218		154 47		155 67		156 4
157 38		158 108		159 14		160 133
161 125		162 49		163 86		164 58
165 45		166 48		167 203		168 31
169 168		170 78		171 235		172 82
173 20		174 190		175 34		176 70
177 159		178 119		179 245		180 177
181 37		182 225		183 240		184 3
185 155		186 81		187 137		188 163
189 157		190 100		191 191		192 170
193 97		194 36		195 89		196 213
197 126		198 185		199 113		200 188
201 15		202 16		203 152		204 179
205 56		206 26		207 247		208 196
209 91		210 232		211 180		212 192
213 53		214 124		215 166		216 59
217 181		218 75		219 80		220 1
221 136		222 27		223 130		224 223
225 221		226 202		227 148		228 141
229 201		230 12		231 114		232 71
233 42		234 146		235 122		236 147
237 5		238 174		239 135		240 144
241 103		242 93		243 251		244 234
245 199		246 246		247 60		248 64
249 102		250 210		251 224		252 104
253 229						

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLT4EaoOA7OpLWtYzAQFBOAQAld1tIOCsDzVtm0XtIiFNOe3vlbj0SeQ6
jcfSXXjKFdxywEbdVsdlGUZNSGy+cWLepzQmZqsNHSF8mDouw+A49CAscYw64GNl
uUmHroRvJ6ABq+Z4GecvUPK3C8X1dTJTrzxqnUdGUZv2sMOAmtgO7LytqurzPzIy
P/N2tK1FDMw=
=UQxw
-----END PGP SIGNATURE-----