# Ticket #11565: rsa_cryptosystem.py

File rsa_cryptosystem.py, 14.3 KB (added by , 8 years ago) |
---|

Line | |
---|---|

1 | r""" |

2 | Rivest, Shamir, Adleman public-key encryption scheme. |

3 | |

4 | The Rivest, Shamir, Adleman public-key encryption scheme. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption. See also the `Wikipedia article <http://en.wikipedia.org/wiki/RSA>`_ on this scheme. |

5 | |

6 | REFERENCES: |

7 | |

8 | .. William Stallings. *Cryptography and Network Security, Priciples and Practices*, Fourth Edition. Prentice Hall, 16 November 2005. |

9 | |

10 | .. Anoop MS. *Public Key Cryptography, Applications Algorithms and Mathematical Explanations*. Tata Elxsi Ltd, India anoopms@tataelxsi.co.in. |

11 | |

12 | .. Minh Van Nguyen. *Number Theory and the RSA Public Key Cryptosystem*. nguyenminh2@gmail.com, July 2009. |

13 | |

14 | AUTHORS: |

15 | |

16 | -Ajeesh R (2011-07)- initial procedural version released as public domain software. |

17 | |

18 | """ |

19 | |

20 | ########################################################################### |

21 | # Copyright (c) 2011 |

22 | # AJEESH R <iamajeeshr@gmail.com> |

23 | # |

24 | # This program is free software; you can redistribute it and/or modify |

25 | # it under the terms of the GNU General Public License as published by |

26 | # the Free Software Foundation; either version 2 of the License, or |

27 | # (at your option) any later version. |

28 | # |

29 | # This program is distributed in the hope that it will be useful, |

30 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |

31 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

32 | # GNU General Public License for more details. |

33 | # |

34 | # http://www.gnu.org/licenses/ |

35 | ########################################################################### |

36 | |

37 | from sage.crypto.cryptosystem import PublicKeyCryptosystem |

38 | from sage.rings.arith import gcd |

39 | from sage.rings.arith import xgcd |

40 | from sage.rings.arith import is_prime |

41 | from sage.rings.arith import power_mod |

42 | from sage.rings.arith import euler_phi |

43 | from sage.rings.integer import Integer |

44 | from sage.rings.finite_rings.integer_mod import Mod as mod |

45 | from sage.rings.integer_ring import ZZ |

46 | |

47 | class RSACryptosystem(PublicKeyCryptosystem): |

48 | r""" |

49 | The Rivest, Shamir, Adleman public-key encryption scheme. |

50 | |

51 | The RSA encryption and decryption algorithms as described in |

52 | :func:`encrypt() <RSACryptosystem.encrypt>` and |

53 | :func:`decrypt() <RSACryptosystem.decrypt>`, respectively, make use of the |

54 | |

55 | EXAMPLES: |

56 | |

57 | The following is an encryption/decryption example.:: |

58 | |

59 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

60 | sage: rc = RSACryptosystem(); rc |

61 | The Rivest, Shamir, Adleman public-key encryption scheme. |

62 | sage: p = 31; q = 61; |

63 | sage: pubkey = rc.public_key(p, q); pubkey |

64 | (4951760154835678088235319297L, 17) |

65 | sage: prikey = rc.private_key(p, q); prikey |

66 | (4951760154835678088235319297L, 4077920125612805357425763753) |

67 | sage: P = 72697676798779827668 |

68 | sage: C = rc.encrypt(P, pubkey); C |

69 | 2467165704948727396791981601 |

70 | sage: M = rc.decrypt(C, prikey); M |

71 | 72697676798779827668 |

72 | sage: M == P |

73 | True |

74 | |

75 | Generate a pair of public/private keys. Use the public key to |

76 | encrypt a plaintext. Then decrypt the resulting ciphertext using the |

77 | private key. Finally, compare the decrypted message with the original |

78 | plaintext.:: |

79 | |

80 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

81 | sage: rc = RSACryptosystem() |

82 | sage: P = 72697676798779827668 |

83 | sage: C = rc.encrypt(P, pubkey) |

84 | sage: M = rc.decrypt(C, prikey) |

85 | sage: M == P |

86 | True |

87 | """ |

88 | |

89 | def __init__(self): |

90 | """ |

91 | Construct the RSA public-key encryption scheme. |

92 | |

93 | OUTPUT: |

94 | |

95 | - A ``RSACryptosystem`` object representing the RSA public-key encryption scheme. |

96 | |

97 | See the class docstring of ``RSACryptosystem`` for detailed documentation. |

98 | |

99 | EXAMPLES:: |

100 | |

101 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

102 | sage: rc = RSACryptosystem() |

103 | sage: rc == loads(dumps(rc)) |

104 | True |

105 | """ |

106 | # no internal data for now; nothing to initialize |

107 | pass |

108 | |

109 | def __eq__(self, other): |

110 | """ |

111 | Compare this ``RSACryptosystem`` object with ``other``. |

112 | |

113 | INPUT: |

114 | |

115 | - ``other`` -- a ``RSACryptosystem`` object. |

116 | |

117 | OUTPUT: |

118 | |

119 | - ``True`` if both ``self`` and ``other`` are ``RSACryptosystem`` |

120 | objects. ``False`` otherwise. |

121 | |

122 | Two objects are ``RSACryptosystem`` objects if their string |

123 | representations are the same. |

124 | |

125 | EXAMPLES:: |

126 | |

127 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

128 | sage: rc1 = RSACryptosystem() |

129 | sage: rc2 = RSACryptosystem() |

130 | sage: rc1 == rc2 |

131 | True |

132 | """ |

133 | if self.__repr__() == other.__repr__(): |

134 | return True |

135 | else: |

136 | return False |

137 | |

138 | def __repr__(self): |

139 | """ |

140 | A string representation of this RSA public-key encryption scheme. |

141 | |

142 | OUTPUT: |

143 | |

144 | - A string representation of this RSA public-key encryption scheme. |

145 | |

146 | EXAMPLES:: |

147 | |

148 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

149 | sage: RSACryptosystem() |

150 | The Rivest, Shamir, Adleman public-key encryption scheme. |

151 | """ |

152 | return "The Rivest, Shamir, Adleman public-key encryption scheme." |

153 | |

154 | def decrypt(self, C, K): |

155 | r""" |

156 | Apply the RSA public-key encryption scheme to decrypt the ciphertext ``C`` |

157 | using the private key ``K``. |

158 | |

159 | INPUT: |

160 | |

161 | - ``C`` -- a ciphertext resulting from encrypting a plaintext using |

162 | the RSA public-key encryption algorithm. |

163 | |

164 | - ``K`` -- a private key `(n, d)` where `n` is the product of two Mersenne |

165 | primes `p` and `q`, `d` is computed using the extended euclidean algorithm. |

166 | |

167 | OUTPUT: |

168 | |

169 | - The plaintext resulting from decrypting the ciphertext ``C`` using |

170 | the RSA public-key decryption algorithm. |

171 | |

172 | ALGORITHM: |

173 | |

174 | The RSA public-key decryption algorithm is described as follows: |

175 | |

176 | #. Let `C` be the ciphertext `C = (M^e) mod n`. |

177 | #. Let `(n, d)` be the private key whose corresponding |

178 | public key is `(n, e)`. |

179 | #. The plaintext is `M = (C^d) mod n`. |

180 | |

181 | EXAMPLES: |

182 | |

183 | The following is a decryption example. Here we decrypt a string of numbers.:: |

184 | |

185 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

186 | sage: rc = RSACryptosystem() |

187 | sage: p = 31; q = 61; |

188 | sage: C = 2467165704948727396791981601 |

189 | sage: K = rc.private_key(p, q); K |

190 | (4951760154835678088235319297L, 4077920125612805357425763753) |

191 | sage: P = rc.decrypt(C, K); P |

192 | 72697676798779827668 |

193 | |

194 | TESTS: |

195 | |

196 | The private key `K = (n, d)` must be such that `p` and `q` are |

197 | distinct prime numbers.:: |

198 | |

199 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

200 | sage: rc = RSACryptosystem() |

201 | sage: C = 2467165704948727396791981601 |

202 | sage: K = rc.private_key(31, 31); |

203 | Traceback (most recent call last): |

204 | ... |

205 | ValueError: p and q must be distinct primes. |

206 | sage: K = rc.private_key(31, 61) |

207 | sage: P = rc.decrypt(C, K); P |

208 | 72697676798779827668 |

209 | """ |

210 | # private key |

211 | (n, d) = K |

212 | |

213 | # perform the decryption |

214 | return power_mod(C, d, n) |

215 | |

216 | def encrypt(self, P, K): |

217 | r""" |

218 | Apply the RSA public-key encryption scheme to encrypt the plaintext ``P`` using |

219 | the public key ``K``. |

220 | |

221 | INPUT: |

222 | |

223 | - ``P`` -- a non-empty string of plaintext. The string ``""`` is |

224 | an empty string, whereas ``" "`` is a string consisting of one |

225 | white space character. The plaintext can be a string of numbers or |

226 | a string of ASCII characters. |

227 | |

228 | - ``K`` -- a public key, which is the product of two Mersenne primes and e, 0 < e < euler_phi(n) |

229 | such that also satisfy the requirement `\gcd(e, euler_phi(n))=1`. |

230 | |

231 | OUTPUT: |

232 | |

233 | - The ciphertext resulting from encrypting ``P`` using the public |

234 | key ``K``. |

235 | |

236 | ALGORITHM: |

237 | |

238 | The RSA public-key encryption algorithm is described as follows: |

239 | |

240 | #. Let `(n, e)` be a public key, where `n = pq` is the product of two |

241 | distinct Mersenne primes `p` and `q` and `e` is a random positive |

242 | integer that is co-prime to euler_phi(n). |

243 | #. Let `P = a string` be the message (plaintext). |

244 | #. The ciphertext is `C = (P^e) mod n`. |

245 | |

246 | |

247 | EXAMPLES: |

248 | |

249 | The following is an encryption example. Here, we encrypt a string of number.:: |

250 | |

251 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

252 | sage: rc = RSACryptosystem() |

253 | sage: p = 101; q = 103; |

254 | sage: P = 4 |

255 | sage: C = rc.encrypt(P, K); C |

256 | 4932417489295796679844298689 |

257 | |

258 | Now encrypt another string of numbers. The result is random; no seed is |

259 | provided to the encryption function so the function generates its |

260 | own random seed.:: |

261 | |

262 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

263 | sage: rc = RSACryptosystem() |

264 | sage: p = 31; q = 61; |

265 | sage: P = 72697676798779827668 |

266 | sage: K = rc.public_key(p, q); |

267 | sage: C = rc.encrypt(P, K); |

268 | sage: C |

269 | 2467165704948727396791981601 |

270 | |

271 | TESTS: |

272 | |

273 | The plaintext cannot be an empty string. :: |

274 | |

275 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

276 | sage: rc = RSACryptosystem() |

277 | sage: rc.encrypt("", 3) |

278 | Traceback (most recent call last): |

279 | ... |

280 | ValueError: The plaintext cannot be an empty string. |

281 | """ |

282 | # public key |

283 | (n, e) = K |

284 | |

285 | # sanity check |

286 | if P == "": |

287 | raise ValueError("The plaintext cannot be an empty string.") |

288 | |

289 | else: |

290 | return power_mod(P, e, n) |

291 | |

292 | def private_key(self, p, q): |

293 | r""" |

294 | Return the RSA private key corresponding to the |

295 | distinct Mersenne primes ``p`` and ``q``. |

296 | |

297 | INPUT: |

298 | |

299 | - ``p`` -- a prime number. |

300 | |

301 | - ``q`` -- a prime number. |

302 | |

303 | OUTPUT: |

304 | |

305 | - The RSA private key `(n, d)` where |

306 | `de is congruent to (1 mod euler_phi(n))`. |

307 | |

308 | Both ``p`` and ``q`` must be distinct primes. Let `p` be a |

309 | positive prime. Then `p` is a Mersenne prime if `p` is equal to `(2^p)-1`. |

310 | |

311 | EXAMPLES: |

312 | |

313 | Obtain two distinct primes and compute the RSA |

314 | private key corresponding to two Mersenne primes generated from the distinct primes.:: |

315 | |

316 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

317 | sage: rc = RSACryptosystem() |

318 | sage: rc.private_key(19, 23) |

319 | (4398037598209L, 1173935455331) |

320 | |

321 | Choose two distinct primes, compute the RSA |

322 | private key corresponding to two Mersenne primes generated from the distinct primes , and test that the |

323 | resulting private key `(n, d)` satisfies |

324 | `\mod(de, euler_phi(n)) = 1`.:: |

325 | |

326 | sage: p = 31 |

327 | sage: q = 61 |

328 | sage: p = (2 ^ p)-1; q = (2 ^ q)-1 |

329 | sage: is_prime(p); is_prime(q) |

330 | True |

331 | True |

332 | |

333 | TESTS: |

334 | |

335 | Both of the input ``p`` and ``q`` must be distinct primes. :: |

336 | |

337 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

338 | sage: rc = RSACryptosystem() |

339 | sage: rc.private_key(78307, 78307) |

340 | Traceback (most recent call last): |

341 | ... |

342 | ValueError: p and q must be distinct primes. |

343 | """ |

344 | if p == q: |

345 | raise ValueError("p and q must be distinct primes.") |

346 | if is_prime(p) and is_prime(q): |

347 | p = (2**p)-1 |

348 | q = (2**q)-1 |

349 | |

350 | n = p * q |

351 | |

352 | e = 3 |

353 | while 1: |

354 | if gcd(euler_phi(n), e) == 1: |

355 | break |

356 | else: |

357 | e = e + 2 |

358 | |

359 | # Generate a number d such that de = 1 (mod euler_phi(n)) |

360 | bezout = xgcd(e, euler_phi(n)) |

361 | d = Integer(mod(bezout[1], euler_phi(n))) |

362 | while mod(d * e, euler_phi(n)) != 1: |

363 | d = Integer(mod(bezout[1], euler_phi(n))) |

364 | else: |

365 | raise ValueError("p and q must be distinct primes.") |

366 | return (n, d) |

367 | |

368 | def public_key(self, p, q): |

369 | r""" |

370 | Return RSA public key corresponding to the |

371 | distinct Mersenne primes ``p`` and ``q``. |

372 | |

373 | INPUT: |

374 | |

375 | - ``p`` -- a prime number. |

376 | |

377 | - ``q`` -- a prime number. |

378 | |

379 | OUTPUT: |

380 | |

381 | - The RSA public key `n = pq` and `e`. |

382 | |

383 | Both ``p`` and ``q`` must be distinct primes. Let `p` be a |

384 | positive prime. Then `p` is a Mersenne prime if `p` is equal to `(2^p)-1`. |

385 | |

386 | EXAMPLES: |

387 | |

388 | Obtain two distinct Mersenne primes and compute the RSA |

389 | public key corresponding to those two Mersenne primes:: |

390 | |

391 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

392 | sage: rc = RSACryptosystem() |

393 | sage: rc.public_key(31, 61) |

394 | (4951760154835678088235319297L, 17) |

395 | |

396 | Choose two distinct primes, compute the RSA |

397 | public key corresponding to two Mersenne primes generated from the distinct primes.:: |

398 | |

399 | sage: p = 31 |

400 | sage: q = 61 |

401 | sage: p = (2 ^ p)-1; q = (2 ^ q)-1 |

402 | sage: is_prime(p); is_prime(q) |

403 | True |

404 | True |

405 | |

406 | TESTS: |

407 | |

408 | The input ``p`` and ``q`` must be distinct primes. :: |

409 | |

410 | sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem |

411 | sage: rc = RSACryptosystem() |

412 | sage: rc.public_key(3, 3) |

413 | Traceback (most recent call last): |

414 | ... |

415 | ValueError: p and q must be distinct primes. |

416 | """ |

417 | if p == q: |

418 | raise ValueError("p and q must be distinct primes.") |

419 | if is_prime(p) and is_prime(q): |

420 | p = (2**p)-1 |

421 | q = (2**q)-1 |

422 | |

423 | n = p * q |

424 | # Generate a number e so that gcd(euler_phi(n), e) = 1 |

425 | e = 3 |

426 | while 1: |

427 | if gcd(euler_phi(n), e) == 1: |

428 | break |

429 | else: |

430 | e = e + 2 |

431 | else: |

432 | raise ValueError("p and q must be distinct primes.") |

433 | return (n, e) |