[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RSA: questions
-----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
[email protected]
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-----