-----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-----