# Ticket #11565: rsa_cryptosystem.2.py

File rsa_cryptosystem.2.py, 22.8 KB (added by , 6 years ago) |
---|

Line | |
---|---|

1 | r""" |

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

3 | |

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

5 | The Rivest-Shamir-Adleman (RSA) scheme is the most widely accepted and |

6 | implemented general-purpose approach to public-key encryption. See also |

7 | the `Wikipedia article <http://en.wikipedia.org/wiki/RSA>`_ on this scheme. |

8 | |

9 | REFERENCES: |

10 | |

11 | .. David Ireland. *RSA Algorithm*. http://www.di-mgt.com.au/rsa_alg.html. 19 March 2015. |

12 | |

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

14 | |

15 | .. Brian Raiter. *Prime Number Hide-and-Seek: How the RSA Cipher Works*. http://www.muppetlabs.com/~breadbox/txt/rsa.html. Accessed 20 March 2015. |

16 | |

17 | .. Thomas Pornin. *Should RSA public exponent be only in {3, 5, 17, 257 or 65537} due to security considerations?*. http://security.stackexchange.com/questions/2335/should-rsa-public-exponent-be-only-in-3-5-17-257-or-65537-due-to-security-c |

18 | |

19 | .. http://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation |

20 | |

21 | |

22 | AUTHORS: |

23 | |

24 | -Peter Story (2015-03)- major rewrite with the goal of a pedagogical implementation. |

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

26 | |

27 | """ |

28 | |

29 | ########################################################################### |

30 | # Copyright (c) 2011 |

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

32 | # |

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

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

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

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

37 | # |

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

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

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

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

42 | # |

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

44 | ########################################################################### |

45 | |

46 | from sage.crypto.cryptosystem import PublicKeyCryptosystem |

47 | from sage.rings.arith import euler_phi |

48 | from sage.rings.arith import gcd |

49 | from sage.rings.arith import is_prime |

50 | from sage.rings.arith import power_mod |

51 | from sage.rings.integer import Integer |

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

53 | from sage.rings.integer_ring import ZZ |

54 | from sage.sets.primes import Primes |

55 | |

56 | class RSACryptosystem(PublicKeyCryptosystem): |

57 | r""" |

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

59 | |

60 | CAN PROBABLY REMOVE THIS |

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

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

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

64 | |

65 | EXAMPLES: |

66 | |

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

68 | |

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

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

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

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

73 | sage: public, private = rc.calculate_keys(p, q); public, private |

74 | ((10403, 257), (10403, 5993)) |

75 | sage: P = 9001 |

76 | sage: C = rc.encrypt(P, public); C |

77 | 6022 |

78 | sage: M = rc.decrypt(C, private); M |

79 | 9001 |

80 | sage: M == P |

81 | True |

82 | """ |

83 | |

84 | def __init__(self): |

85 | """ |

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

87 | |

88 | OUTPUT: |

89 | |

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

91 | |

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

93 | |

94 | EXAMPLES:: |

95 | |

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

97 | sage: rc = RSACryptosystem() |

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

99 | True |

100 | """ |

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

102 | pass |

103 | |

104 | def __eq__(self, other): |

105 | """ |

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

107 | |

108 | INPUT: |

109 | |

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

111 | |

112 | OUTPUT: |

113 | |

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

115 | objects. ``False`` otherwise. |

116 | |

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

118 | representations are the same. |

119 | |

120 | EXAMPLES:: |

121 | |

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

123 | sage: rc1 = RSACryptosystem() |

124 | sage: rc2 = RSACryptosystem() |

125 | sage: rc1 == rc2 |

126 | True |

127 | """ |

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

129 | return True |

130 | else: |

131 | return False |

132 | |

133 | def __repr__(self): |

134 | """ |

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

136 | |

137 | OUTPUT: |

138 | |

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

140 | |

141 | EXAMPLES:: |

142 | |

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

144 | sage: RSACryptosystem() |

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

146 | """ |

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

148 | |

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

150 | r""" |

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

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

153 | |

154 | INPUT: |

155 | |

156 | - ``C`` -- an integer ciphertext resulting from encrypting a plaintext |

157 | using the RSA public-key encryption algorithm. |

158 | |

159 | - ``K`` -- a private key, stored as a tuple ``(n, d)`` where ``n`` |

160 | is the modulus and ``d`` is inverse of the exponent ``mod (phi(n))``. |

161 | |

162 | OUTPUT: |

163 | |

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

165 | the RSA public-key decryption algorithm. |

166 | |

167 | ALGORITHM: |

168 | |

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

170 | |

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

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

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

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

175 | |

176 | EXAMPLES: |

177 | |

178 | An example of decryption.:: |

179 | |

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

181 | sage: rc = RSACryptosystem() |

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

183 | sage: public, private = rc.calculate_keys(p, q) |

184 | sage: P = 42 |

185 | sage: C = rc.encrypt(P, public); C |

186 | 6270 |

187 | sage: M = rc.decrypt(C, private); M; P == M |

188 | 42 |

189 | True |

190 | |

191 | TESTS: |

192 | |

193 | Decryption should recover the original message.:: |

194 | |

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

196 | sage: rc = RSACryptosystem() |

197 | sage: p = 101; q = 103; n = p * q |

198 | sage: public, private = rc.calculate_keys(p, q) |

199 | sage: P = 42 |

200 | sage: C = rc.encrypt(P, public) |

201 | sage: rc.decrypt(C, private) == P |

202 | True |

203 | sage: P = ZZ.random_element(2, n) |

204 | sage: C = rc.encrypt(P, public) |

205 | sage: rc.decrypt(C, private) == P |

206 | True |

207 | |

208 | Ciphertext outside the range ``[2, n-1]`` should be rejected.:: |

209 | |

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

211 | sage: rc = RSACryptosystem() |

212 | sage: p = 101; q = 103; n = p * q |

213 | sage: public, private = rc.calculate_keys(p, q) |

214 | sage: C = -5; rc.decrypt(C, private) |

215 | Traceback (most recent call last): |

216 | ... |

217 | ValueError: The ciphertext must be an integer greater than 1 and less than n. |

218 | |

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

220 | sage: rc = RSACryptosystem() |

221 | sage: p = 101; q = 103; n = p * q |

222 | sage: public, private = rc.calculate_keys(p, q) |

223 | sage: C = 0; rc.decrypt(C, private) |

224 | Traceback (most recent call last): |

225 | ... |

226 | ValueError: The ciphertext must be an integer greater than 1 and less than n. |

227 | |

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

229 | sage: rc = RSACryptosystem() |

230 | sage: p = 101; q = 103; n = p * q |

231 | sage: public, private = rc.calculate_keys(p, q) |

232 | sage: C = 1; rc.decrypt(C, private) |

233 | Traceback (most recent call last): |

234 | ... |

235 | ValueError: The ciphertext must be an integer greater than 1 and less than n. |

236 | |

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

238 | sage: rc = RSACryptosystem() |

239 | sage: p = 101; q = 103; n = p * q |

240 | sage: public, private = rc.calculate_keys(p, q) |

241 | sage: C = n; rc.decrypt(C, private) |

242 | Traceback (most recent call last): |

243 | ... |

244 | ValueError: The ciphertext must be an integer greater than 1 and less than n. |

245 | |

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

247 | sage: rc = RSACryptosystem() |

248 | sage: p = 101; q = 103; n = p * q |

249 | sage: public, private = rc.calculate_keys(p, q) |

250 | sage: C = n + 5; rc.decrypt(C, private) |

251 | Traceback (most recent call last): |

252 | ... |

253 | ValueError: The ciphertext must be an integer greater than 1 and less than n. |

254 | |

255 | |

256 | Ciphertext in the range ``[2, n-1]`` should be accepted.:: |

257 | |

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

259 | sage: rc = RSACryptosystem() |

260 | sage: p = 101; q = 103; n = p * q |

261 | sage: public, private = rc.calculate_keys(p, q) |

262 | sage: C = 2; M = rc.decrypt(C, private) |

263 | sage: C = n - 1; M = rc.decrypt(C, private) |

264 | sage: C = ZZ.random_element(2, n); M = rc.decrypt(C, private) |

265 | |

266 | """ |

267 | # private key |

268 | (n, d) = K |

269 | |

270 | # sanity check |

271 | if (C < 2) or (C >= n): |

272 | raise ValueError("The ciphertext must be an integer greater than 1 and less than n.") |

273 | |

274 | # perform the decryption |

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

276 | |

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

278 | r""" |

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

280 | the public key ``K``. |

281 | |

282 | INPUT: |

283 | |

284 | - ``P`` -- a number in the range ``[2, n-1]``. Note that a secure |

285 | implementation of the cryptosystem would add padding to this |

286 | plaintext, in order to protect against a number of attacks. |

287 | |

288 | - ``K`` -- a public key, stored as a tuple ``(n, e)`` where ``n`` |

289 | is the modulus and ``e`` is the exponent. |

290 | |

291 | OUTPUT: |

292 | |

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

294 | key ``K``. |

295 | |

296 | ALGORITHM: |

297 | |

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

299 | |

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

301 | distinct primes `p` and `q` and exponent `e` is a positive |

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

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

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

305 | |

306 | |

307 | EXAMPLES: |

308 | |

309 | An example of encryption. |

310 | ``P = 42`` is our plaintext, and ``C = 6270`` is the resulting ciphertext.:: |

311 | |

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

313 | sage: rc = RSACryptosystem() |

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

315 | sage: public, private = rc.calculate_keys(p, q) |

316 | sage: P = 42 |

317 | sage: C = rc.encrypt(P, public); C |

318 | 6270 |

319 | |

320 | |

321 | If the system allowed us to encrypt values greater than ``n-1``, our |

322 | message could be encrypted to the same value a different messsage. |

323 | ``P_1`` is our first plaintext, and ``P_2`` is a plaintext greater than |

324 | ``n - 1``, so it isn't encypted to a distinct value.:: |

325 | |

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

327 | sage: rc = RSACryptosystem() |

328 | sage: p = 101; q = 103; n = p * q |

329 | sage: public, private = rc.calculate_keys(p, q) |

330 | sage: e = public[1] |

331 | sage: P_1 = 42 |

332 | sage: P_2 = 42 + n |

333 | sage: C_1 = power_mod(P_1, e, n); C_1 |

334 | 6270 |

335 | sage: C_2 = power_mod(P_2, e, n); C_2 |

336 | 6270 |

337 | sage: C_1 == C_2 |

338 | True |

339 | |

340 | |

341 | TESTS: |

342 | |

343 | Plaintext outside the range ``[2, n-1]`` should be rejected.:: |

344 | |

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

346 | sage: rc = RSACryptosystem() |

347 | sage: p = 101; q = 103; n = p * q |

348 | sage: public, private = rc.calculate_keys(p, q) |

349 | sage: P = -5; rc.encrypt(P, public) |

350 | Traceback (most recent call last): |

351 | ... |

352 | ValueError: The plaintext must be an integer greater than 1 and less than n. |

353 | |

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

355 | sage: rc = RSACryptosystem() |

356 | sage: p = 101; q = 103; n = p * q |

357 | sage: public, private = rc.calculate_keys(p, q) |

358 | sage: P = 0; rc.encrypt(P, public) |

359 | Traceback (most recent call last): |

360 | ... |

361 | ValueError: The plaintext must be an integer greater than 1 and less than n. |

362 | |

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

364 | sage: rc = RSACryptosystem() |

365 | sage: p = 101; q = 103; n = p * q |

366 | sage: public, private = rc.calculate_keys(p, q) |

367 | sage: P = 1; rc.encrypt(P, public) |

368 | Traceback (most recent call last): |

369 | ... |

370 | ValueError: The plaintext must be an integer greater than 1 and less than n. |

371 | |

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

373 | sage: rc = RSACryptosystem() |

374 | sage: p = 101; q = 103; n = p * q |

375 | sage: public, private = rc.calculate_keys(p, q) |

376 | sage: P = n; rc.encrypt(P, public) |

377 | Traceback (most recent call last): |

378 | ... |

379 | ValueError: The plaintext must be an integer greater than 1 and less than n. |

380 | |

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

382 | sage: rc = RSACryptosystem() |

383 | sage: p = 101; q = 103; n = p * q |

384 | sage: public, private = rc.calculate_keys(p, q) |

385 | sage: P = n + 5; rc.encrypt(P, public) |

386 | Traceback (most recent call last): |

387 | ... |

388 | ValueError: The plaintext must be an integer greater than 1 and less than n. |

389 | |

390 | |

391 | Plaintext in the range ``[2, n-1]`` should be accepted.:: |

392 | |

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

394 | sage: rc = RSACryptosystem() |

395 | sage: p = 101; q = 103; n = p * q |

396 | sage: public, private = rc.calculate_keys(p, q) |

397 | sage: P = 2; C = rc.encrypt(P, public) |

398 | sage: P = n - 1; C = rc.encrypt(P, public) |

399 | sage: P = ZZ.random_element(2, n); C = rc.encrypt(P, public) |

400 | |

401 | """ |

402 | # public key |

403 | n, e = K |

404 | |

405 | # sanity check |

406 | if (P < 2) or (P >= n): |

407 | raise ValueError("The plaintext must be an integer greater than 1 and less than n.") |

408 | |

409 | # Encrypt and return the message |

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

411 | |

412 | def choose_exponent(self, phi_n): |

413 | """ |

414 | Choose an exponent relatively prime to the Euler |

415 | Characteristic of ``n``. |

416 | |

417 | Using a small number is not a security problem. For pedagogical |

418 | purposes, we include two different ways of finding ``e``. |

419 | |

420 | INPUT: |

421 | |

422 | - ``phi_n`` -- the Euler Characteristic of ``n`` |

423 | |

424 | OUTPUT: |

425 | |

426 | - A number relatively prime to ``phi_n`` |

427 | |

428 | |

429 | EXAMPLES: |

430 | |

431 | Get a number relatively prime to ``phi_n``. |

432 | |

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

434 | sage: rc = RSACryptosystem() |

435 | sage: phi_n = 11020 |

436 | sage: e = rc.choose_exponent(phi_n) |

437 | sage: gcd(phi_n, e) == 1 |

438 | True |

439 | |

440 | TESTS: |

441 | |

442 | The returned value must be relatively prime to ``phi_n``:: |

443 | |

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

445 | sage: rc = RSACryptosystem() |

446 | sage: phi_n = ZZ.random_element(50, 100) |

447 | sage: e = rc.choose_exponent(phi_n) |

448 | sage: gcd(phi_n, e) == 1 |

449 | True |

450 | |

451 | |

452 | Exercise the second method of finding a relatively prime exponent.:: |

453 | |

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

455 | sage: rc = RSACryptosystem() |

456 | sage: e_options = [3, 5, 17, 257, 65537] |

457 | sage: phi_n = prod(e_options) |

458 | sage: e = rc.choose_exponent(phi_n) |

459 | sage: gcd(phi_n, e) == 1 |

460 | True |

461 | sage: e not in e_options |

462 | True |

463 | |

464 | """ |

465 | # Several recommendations for e, according to the SSL specification |

466 | e_options = [3, 5, 17, 257, 65537] |

467 | # Seeking an e such that phi_n and e are coprime |

468 | for e_option in e_options: |

469 | # Since each e_option is a prime, we can check efficiently |

470 | # check coprimeness; the only way they wouldn't be coprime would |

471 | # be if phi_n was a multiple of the e_option |

472 | if ((phi_n % e_option) != 0): # They are coprime |

473 | return e_option |

474 | |

475 | # It is unlikely that none of the e_options will work, but just in case |

476 | # we provide the option to seek additional values. |

477 | P = Primes() |

478 | p = P.first() |

479 | while (phi_n % p == 0): |

480 | p = P.next(p) |

481 | return p |

482 | |

483 | def calculate_keys(self, p, q, enforce_primes=True): |

484 | r""" |

485 | Return an RSA public and private key pair corresponding to the |

486 | distinct primes ``p`` and ``q``. |

487 | |

488 | INPUT: |

489 | |

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

491 | |

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

493 | |

494 | OUTPUT: |

495 | |

496 | - The RSA public and private keys as a tuple `((n, e), (n, d))`. |

497 | |

498 | |

499 | EXAMPLES: |

500 | |

501 | Compute an RSA public and private key pair corresponding to the |

502 | supplied primes. The ``d`` in the private key should be the |

503 | multiplicative inverse of ``e`` mod ``\phi(n)``:: |

504 | |

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

506 | sage: rc = RSACryptosystem() |

507 | sage: public, private = rc.calculate_keys(19, 23); public, private |

508 | ((437, 5), (437, 317)) |

509 | sage: n = public[0]; e = public[1]; d = private[1] |

510 | sage: (e * d) % euler_phi(n) |

511 | 1 |

512 | |

513 | For teaching purposes, you can supply two numbers that are not primes. |

514 | This is also helpful if you are using very large primes, to avoid the |

515 | expensive computation of checking primeness. |

516 | In this example, we use prime ``17`` and Carmichael number |

517 | ``561 = 3 * 11 * 17`` to generate the keys. Note that decrypting |

518 | doesn't recover the original plaintext.:: |

519 | |

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

521 | sage: rc = RSACryptosystem() |

522 | sage: public, private = rc.calculate_keys(17, 561, False); public, private |

523 | ((9537, 3), (9537, 2987)) |

524 | sage: P = 1234 |

525 | sage: C = rc.encrypt(P, public); C |

526 | 5794 |

527 | sage: M = rc.decrypt(C, private); M |

528 | 5722 |

529 | |

530 | In this example we use ``p`` and ``q`` which are relatively prime, but |

531 | ``p`` is not a prime. In this case, only certain plaintexts can be |

532 | recovered.:: |

533 | |

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

535 | sage: rc = RSACryptosystem() |

536 | sage: public, private = rc.calculate_keys(4, 19, False); public, private |

537 | ((76, 5), (76, 11)) |

538 | sage: P = 10 |

539 | sage: M = rc.decrypt(rc.encrypt(P, public), private); M |

540 | 48 |

541 | sage: P = 24 |

542 | sage: M = rc.decrypt(rc.encrypt(P, public), private); M |

543 | 24 |

544 | |

545 | However, it is also possible to be build a cryptosystem using a |

546 | composite which works for all plaintexts.:: |

547 | |

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

549 | sage: rc = RSACryptosystem() |

550 | sage: public, private = rc.calculate_keys(5, 6, False) |

551 | sage: n = public[0] |

552 | sage: fail_count = 0 |

553 | sage: for P in range(2, n): |

554 | ....: if P != rc.decrypt(rc.encrypt(P, public), private): |

555 | ....: fail_count += 1 |

556 | sage: fail_count |

557 | 0 |

558 | |

559 | TESTS: |

560 | |

561 | Both of the inputs ``p`` and ``q`` must be distinct.:: |

562 | |

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

564 | sage: rc = RSACryptosystem() |

565 | sage: rc.calculate_keys(23, 23) |

566 | Traceback (most recent call last): |

567 | ... |

568 | ValueError: p and q must be distinct. |

569 | |

570 | |

571 | Both of the inputs ``p`` and ``q`` must be prime.:: |

572 | |

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

574 | sage: rc = RSACryptosystem() |

575 | sage: rc.calculate_keys(13, 21) |

576 | Traceback (most recent call last): |

577 | ... |

578 | ValueError: p and q must be primes. |

579 | |

580 | Allow ``p`` or ``q`` to be composite if ``enforce_primes`` is set |

581 | to ``False``.:: |

582 | |

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

584 | sage: rc = RSACryptosystem() |

585 | sage: rc.calculate_keys(13, 21, False) |

586 | ((273, 17), (273, 113)) |

587 | |

588 | The ``d`` in the private key should be the multiplicative inverse |

589 | of ``e`` mod ``\phi(n)``:: |

590 | |

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

592 | sage: rc = RSACryptosystem() |

593 | sage: p = next_prime(ZZ.random_element(50, 100)); q = next_prime(ZZ.random_element(150, 200)) |

594 | sage: public, private = rc.calculate_keys(p, q) |

595 | sage: n = public[0]; e = public[1]; d = private[1] |

596 | sage: (e * d) % euler_phi(n) |

597 | 1 |

598 | |

599 | """ |

600 | if p == q: |

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

602 | # Unsure of the following comment: |

603 | # Unfortunately, we cannot enforce the primeness of ``p`` and ``q``, |

604 | # since primeness cannot be efficiently verified for large primes.:: |

605 | if enforce_primes and ((not is_prime(p)) or (not is_prime(q))): |

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

607 | |

608 | n = p * q |

609 | # Compute the Euler Characteristic of ``n`` |

610 | # We can compute this efficiently because we know ``p`` and ``q`` |

611 | phi_n = (p - 1) * (q - 1) |

612 | |

613 | # Chooses an ``e`` relative prime to ``phi_n`` |

614 | e = self.choose_exponent(phi_n) |

615 | |

616 | # Generate a number ``d`` such that ``de = 1 mod (\phi(n))`` |

617 | # ``d`` serves as our decryption key, contained in the private key; |

618 | # it is the multiplicative inverse of ``e`` |

619 | |

620 | # Get the multiplicative inverse of ``e mod (\phi(n))`` |

621 | d = power_mod(e, -1, phi_n) |

622 | |

623 | private_key = (n, d) |

624 | public_key = (n, e) |

625 | return (public_key, private_key) |