1""" 2This file contains some classical ciphers and routines 3implementing a linear-feedback shift register (LFSR) 4and the Diffie-Hellman key exchange. 5 6.. warning:: 7 8 This module is intended for educational purposes only. Do not use the 9 functions in this module for real cryptographic applications. If you wish 10 to encrypt real data, we recommend using something like the `cryptography 11 <https://cryptography.io/en/latest/>`_ module. 12 13""" 14 15from string import whitespace, ascii_uppercase as uppercase, printable 16from functools import reduce 17import warnings 18 19from itertools import cycle 20 21from sympy import nextprime 22from sympy.core import Rational, Symbol 23from sympy.core.numbers import igcdex, mod_inverse, igcd 24from sympy.core.compatibility import as_int 25from sympy.matrices import Matrix 26from sympy.ntheory import isprime, primitive_root, factorint 27from sympy.polys.domains import FF 28from sympy.polys.polytools import gcd, Poly 29from sympy.utilities.misc import filldedent, translate 30from sympy.utilities.iterables import uniq, multiset 31from sympy.testing.randtest import _randrange, _randint 32 33 34class NonInvertibleCipherWarning(RuntimeWarning): 35 """A warning raised if the cipher is not invertible.""" 36 def __init__(self, msg): 37 self.fullMessage = msg 38 39 def __str__(self): 40 return '\n\t' + self.fullMessage 41 42 def warn(self, stacklevel=2): 43 warnings.warn(self, stacklevel=stacklevel) 44 45 46def AZ(s=None): 47 """Return the letters of ``s`` in uppercase. In case more than 48 one string is passed, each of them will be processed and a list 49 of upper case strings will be returned. 50 51 Examples 52 ======== 53 54 >>> from sympy.crypto.crypto import AZ 55 >>> AZ('Hello, world!') 56 'HELLOWORLD' 57 >>> AZ('Hello, world!'.split()) 58 ['HELLO', 'WORLD'] 59 60 See Also 61 ======== 62 63 check_and_join 64 65 """ 66 if not s: 67 return uppercase 68 t = type(s) is str 69 if t: 70 s = [s] 71 rv = [check_and_join(i.upper().split(), uppercase, filter=True) 72 for i in s] 73 if t: 74 return rv[0] 75 return rv 76 77bifid5 = AZ().replace('J', '') 78bifid6 = AZ() + '0123456789' 79bifid10 = printable 80 81 82def padded_key(key, symbols): 83 """Return a string of the distinct characters of ``symbols`` with 84 those of ``key`` appearing first. A ValueError is raised if 85 a) there are duplicate characters in ``symbols`` or 86 b) there are characters in ``key`` that are not in ``symbols``. 87 88 Examples 89 ======== 90 91 >>> from sympy.crypto.crypto import padded_key 92 >>> padded_key('PUPPY', 'OPQRSTUVWXY') 93 'PUYOQRSTVWX' 94 >>> padded_key('RSA', 'ARTIST') 95 Traceback (most recent call last): 96 ... 97 ValueError: duplicate characters in symbols: T 98 99 """ 100 syms = list(uniq(symbols)) 101 if len(syms) != len(symbols): 102 extra = ''.join(sorted({ 103 i for i in symbols if symbols.count(i) > 1})) 104 raise ValueError('duplicate characters in symbols: %s' % extra) 105 extra = set(key) - set(syms) 106 if extra: 107 raise ValueError( 108 'characters in key but not symbols: %s' % ''.join( 109 sorted(extra))) 110 key0 = ''.join(list(uniq(key))) 111 # remove from syms characters in key0 112 return key0 + translate(''.join(syms), None, key0) 113 114 115def check_and_join(phrase, symbols=None, filter=None): 116 """ 117 Joins characters of ``phrase`` and if ``symbols`` is given, raises 118 an error if any character in ``phrase`` is not in ``symbols``. 119 120 Parameters 121 ========== 122 123 phrase 124 String or list of strings to be returned as a string. 125 126 symbols 127 Iterable of characters allowed in ``phrase``. 128 129 If ``symbols`` is ``None``, no checking is performed. 130 131 Examples 132 ======== 133 134 >>> from sympy.crypto.crypto import check_and_join 135 >>> check_and_join('a phrase') 136 'a phrase' 137 >>> check_and_join('a phrase'.upper().split()) 138 'APHRASE' 139 >>> check_and_join('a phrase!'.upper().split(), 'ARE', filter=True) 140 'ARAE' 141 >>> check_and_join('a phrase!'.upper().split(), 'ARE') 142 Traceback (most recent call last): 143 ... 144 ValueError: characters in phrase but not symbols: "!HPS" 145 146 """ 147 rv = ''.join(''.join(phrase)) 148 if symbols is not None: 149 symbols = check_and_join(symbols) 150 missing = ''.join(list(sorted(set(rv) - set(symbols)))) 151 if missing: 152 if not filter: 153 raise ValueError( 154 'characters in phrase but not symbols: "%s"' % missing) 155 rv = translate(rv, None, missing) 156 return rv 157 158 159def _prep(msg, key, alp, default=None): 160 if not alp: 161 if not default: 162 alp = AZ() 163 msg = AZ(msg) 164 key = AZ(key) 165 else: 166 alp = default 167 else: 168 alp = ''.join(alp) 169 key = check_and_join(key, alp, filter=True) 170 msg = check_and_join(msg, alp, filter=True) 171 return msg, key, alp 172 173 174def cycle_list(k, n): 175 """ 176 Returns the elements of the list ``range(n)`` shifted to the 177 left by ``k`` (so the list starts with ``k`` (mod ``n``)). 178 179 Examples 180 ======== 181 182 >>> from sympy.crypto.crypto import cycle_list 183 >>> cycle_list(3, 10) 184 [3, 4, 5, 6, 7, 8, 9, 0, 1, 2] 185 186 """ 187 k = k % n 188 return list(range(k, n)) + list(range(k)) 189 190 191######## shift cipher examples ############ 192 193 194def encipher_shift(msg, key, symbols=None): 195 """ 196 Performs shift cipher encryption on plaintext msg, and returns the 197 ciphertext. 198 199 Parameters 200 ========== 201 202 key : int 203 The secret key. 204 205 msg : str 206 Plaintext of upper-case letters. 207 208 Returns 209 ======= 210 211 str 212 Ciphertext of upper-case letters. 213 214 Examples 215 ======== 216 217 >>> from sympy.crypto.crypto import encipher_shift, decipher_shift 218 >>> msg = "GONAVYBEATARMY" 219 >>> ct = encipher_shift(msg, 1); ct 220 'HPOBWZCFBUBSNZ' 221 222 To decipher the shifted text, change the sign of the key: 223 224 >>> encipher_shift(ct, -1) 225 'GONAVYBEATARMY' 226 227 There is also a convenience function that does this with the 228 original key: 229 230 >>> decipher_shift(ct, 1) 231 'GONAVYBEATARMY' 232 233 Notes 234 ===== 235 236 ALGORITHM: 237 238 STEPS: 239 0. Number the letters of the alphabet from 0, ..., N 240 1. Compute from the string ``msg`` a list ``L1`` of 241 corresponding integers. 242 2. Compute from the list ``L1`` a new list ``L2``, given by 243 adding ``(k mod 26)`` to each element in ``L1``. 244 3. Compute from the list ``L2`` a string ``ct`` of 245 corresponding letters. 246 247 The shift cipher is also called the Caesar cipher, after 248 Julius Caesar, who, according to Suetonius, used it with a 249 shift of three to protect messages of military significance. 250 Caesar's nephew Augustus reportedly used a similar cipher, but 251 with a right shift of 1. 252 253 References 254 ========== 255 256 .. [1] https://en.wikipedia.org/wiki/Caesar_cipher 257 .. [2] http://mathworld.wolfram.com/CaesarsMethod.html 258 259 See Also 260 ======== 261 262 decipher_shift 263 264 """ 265 msg, _, A = _prep(msg, '', symbols) 266 shift = len(A) - key % len(A) 267 key = A[shift:] + A[:shift] 268 return translate(msg, key, A) 269 270 271def decipher_shift(msg, key, symbols=None): 272 """ 273 Return the text by shifting the characters of ``msg`` to the 274 left by the amount given by ``key``. 275 276 Examples 277 ======== 278 279 >>> from sympy.crypto.crypto import encipher_shift, decipher_shift 280 >>> msg = "GONAVYBEATARMY" 281 >>> ct = encipher_shift(msg, 1); ct 282 'HPOBWZCFBUBSNZ' 283 284 To decipher the shifted text, change the sign of the key: 285 286 >>> encipher_shift(ct, -1) 287 'GONAVYBEATARMY' 288 289 Or use this function with the original key: 290 291 >>> decipher_shift(ct, 1) 292 'GONAVYBEATARMY' 293 294 """ 295 return encipher_shift(msg, -key, symbols) 296 297def encipher_rot13(msg, symbols=None): 298 """ 299 Performs the ROT13 encryption on a given plaintext ``msg``. 300 301 Explanation 302 =========== 303 304 ROT13 is a substitution cipher which substitutes each letter 305 in the plaintext message for the letter furthest away from it 306 in the English alphabet. 307 308 Equivalently, it is just a Caeser (shift) cipher with a shift 309 key of 13 (midway point of the alphabet). 310 311 References 312 ========== 313 314 .. [1] https://en.wikipedia.org/wiki/ROT13 315 316 See Also 317 ======== 318 319 decipher_rot13 320 encipher_shift 321 322 """ 323 return encipher_shift(msg, 13, symbols) 324 325def decipher_rot13(msg, symbols=None): 326 """ 327 Performs the ROT13 decryption on a given plaintext ``msg``. 328 329 Explanation 330 ============ 331 332 ``decipher_rot13`` is equivalent to ``encipher_rot13`` as both 333 ``decipher_shift`` with a key of 13 and ``encipher_shift`` key with a 334 key of 13 will return the same results. Nonetheless, 335 ``decipher_rot13`` has nonetheless been explicitly defined here for 336 consistency. 337 338 Examples 339 ======== 340 341 >>> from sympy.crypto.crypto import encipher_rot13, decipher_rot13 342 >>> msg = 'GONAVYBEATARMY' 343 >>> ciphertext = encipher_rot13(msg);ciphertext 344 'TBANILORNGNEZL' 345 >>> decipher_rot13(ciphertext) 346 'GONAVYBEATARMY' 347 >>> encipher_rot13(msg) == decipher_rot13(msg) 348 True 349 >>> msg == decipher_rot13(ciphertext) 350 True 351 352 """ 353 return decipher_shift(msg, 13, symbols) 354 355######## affine cipher examples ############ 356 357 358def encipher_affine(msg, key, symbols=None, _inverse=False): 359 r""" 360 Performs the affine cipher encryption on plaintext ``msg``, and 361 returns the ciphertext. 362 363 Explanation 364 =========== 365 366 Encryption is based on the map `x \rightarrow ax+b` (mod `N`) 367 where ``N`` is the number of characters in the alphabet. 368 Decryption is based on the map `x \rightarrow cx+d` (mod `N`), 369 where `c = a^{-1}` (mod `N`) and `d = -a^{-1}b` (mod `N`). 370 In particular, for the map to be invertible, we need 371 `\mathrm{gcd}(a, N) = 1` and an error will be raised if this is 372 not true. 373 374 Parameters 375 ========== 376 377 msg : str 378 Characters that appear in ``symbols``. 379 380 a, b : int, int 381 A pair integers, with ``gcd(a, N) = 1`` (the secret key). 382 383 symbols 384 String of characters (default = uppercase letters). 385 386 When no symbols are given, ``msg`` is converted to upper case 387 letters and all other characters are ignored. 388 389 Returns 390 ======= 391 392 ct 393 String of characters (the ciphertext message) 394 395 Notes 396 ===== 397 398 ALGORITHM: 399 400 STEPS: 401 0. Number the letters of the alphabet from 0, ..., N 402 1. Compute from the string ``msg`` a list ``L1`` of 403 corresponding integers. 404 2. Compute from the list ``L1`` a new list ``L2``, given by 405 replacing ``x`` by ``a*x + b (mod N)``, for each element 406 ``x`` in ``L1``. 407 3. Compute from the list ``L2`` a string ``ct`` of 408 corresponding letters. 409 410 This is a straightforward generalization of the shift cipher with 411 the added complexity of requiring 2 characters to be deciphered in 412 order to recover the key. 413 414 References 415 ========== 416 417 .. [1] https://en.wikipedia.org/wiki/Affine_cipher 418 419 See Also 420 ======== 421 422 decipher_affine 423 424 """ 425 msg, _, A = _prep(msg, '', symbols) 426 N = len(A) 427 a, b = key 428 assert gcd(a, N) == 1 429 if _inverse: 430 c = mod_inverse(a, N) 431 d = -b*c 432 a, b = c, d 433 B = ''.join([A[(a*i + b) % N] for i in range(N)]) 434 return translate(msg, A, B) 435 436 437def decipher_affine(msg, key, symbols=None): 438 r""" 439 Return the deciphered text that was made from the mapping, 440 `x \rightarrow ax+b` (mod `N`), where ``N`` is the 441 number of characters in the alphabet. Deciphering is done by 442 reciphering with a new key: `x \rightarrow cx+d` (mod `N`), 443 where `c = a^{-1}` (mod `N`) and `d = -a^{-1}b` (mod `N`). 444 445 Examples 446 ======== 447 448 >>> from sympy.crypto.crypto import encipher_affine, decipher_affine 449 >>> msg = "GO NAVY BEAT ARMY" 450 >>> key = (3, 1) 451 >>> encipher_affine(msg, key) 452 'TROBMVENBGBALV' 453 >>> decipher_affine(_, key) 454 'GONAVYBEATARMY' 455 456 See Also 457 ======== 458 459 encipher_affine 460 461 """ 462 return encipher_affine(msg, key, symbols, _inverse=True) 463 464 465def encipher_atbash(msg, symbols=None): 466 r""" 467 Enciphers a given ``msg`` into its Atbash ciphertext and returns it. 468 469 Explanation 470 =========== 471 472 Atbash is a substitution cipher originally used to encrypt the Hebrew 473 alphabet. Atbash works on the principle of mapping each alphabet to its 474 reverse / counterpart (i.e. a would map to z, b to y etc.) 475 476 Atbash is functionally equivalent to the affine cipher with ``a = 25`` 477 and ``b = 25`` 478 479 See Also 480 ======== 481 482 decipher_atbash 483 484 """ 485 return encipher_affine(msg, (25, 25), symbols) 486 487 488def decipher_atbash(msg, symbols=None): 489 r""" 490 Deciphers a given ``msg`` using Atbash cipher and returns it. 491 492 Explanation 493 =========== 494 495 ``decipher_atbash`` is functionally equivalent to ``encipher_atbash``. 496 However, it has still been added as a separate function to maintain 497 consistency. 498 499 Examples 500 ======== 501 502 >>> from sympy.crypto.crypto import encipher_atbash, decipher_atbash 503 >>> msg = 'GONAVYBEATARMY' 504 >>> encipher_atbash(msg) 505 'TLMZEBYVZGZINB' 506 >>> decipher_atbash(msg) 507 'TLMZEBYVZGZINB' 508 >>> encipher_atbash(msg) == decipher_atbash(msg) 509 True 510 >>> msg == encipher_atbash(encipher_atbash(msg)) 511 True 512 513 References 514 ========== 515 516 .. [1] https://en.wikipedia.org/wiki/Atbash 517 518 See Also 519 ======== 520 521 encipher_atbash 522 523 """ 524 return decipher_affine(msg, (25, 25), symbols) 525 526#################### substitution cipher ########################### 527 528 529def encipher_substitution(msg, old, new=None): 530 r""" 531 Returns the ciphertext obtained by replacing each character that 532 appears in ``old`` with the corresponding character in ``new``. 533 If ``old`` is a mapping, then new is ignored and the replacements 534 defined by ``old`` are used. 535 536 Explanation 537 =========== 538 539 This is a more general than the affine cipher in that the key can 540 only be recovered by determining the mapping for each symbol. 541 Though in practice, once a few symbols are recognized the mappings 542 for other characters can be quickly guessed. 543 544 Examples 545 ======== 546 547 >>> from sympy.crypto.crypto import encipher_substitution, AZ 548 >>> old = 'OEYAG' 549 >>> new = '034^6' 550 >>> msg = AZ("go navy! beat army!") 551 >>> ct = encipher_substitution(msg, old, new); ct 552 '60N^V4B3^T^RM4' 553 554 To decrypt a substitution, reverse the last two arguments: 555 556 >>> encipher_substitution(ct, new, old) 557 'GONAVYBEATARMY' 558 559 In the special case where ``old`` and ``new`` are a permutation of 560 order 2 (representing a transposition of characters) their order 561 is immaterial: 562 563 >>> old = 'NAVY' 564 >>> new = 'ANYV' 565 >>> encipher = lambda x: encipher_substitution(x, old, new) 566 >>> encipher('NAVY') 567 'ANYV' 568 >>> encipher(_) 569 'NAVY' 570 571 The substitution cipher, in general, is a method 572 whereby "units" (not necessarily single characters) of plaintext 573 are replaced with ciphertext according to a regular system. 574 575 >>> ords = dict(zip('abc', ['\\%i' % ord(i) for i in 'abc'])) 576 >>> print(encipher_substitution('abc', ords)) 577 \97\98\99 578 579 References 580 ========== 581 582 .. [1] https://en.wikipedia.org/wiki/Substitution_cipher 583 584 """ 585 return translate(msg, old, new) 586 587 588###################################################################### 589#################### Vigenere cipher examples ######################## 590###################################################################### 591 592def encipher_vigenere(msg, key, symbols=None): 593 """ 594 Performs the Vigenere cipher encryption on plaintext ``msg``, and 595 returns the ciphertext. 596 597 Examples 598 ======== 599 600 >>> from sympy.crypto.crypto import encipher_vigenere, AZ 601 >>> key = "encrypt" 602 >>> msg = "meet me on monday" 603 >>> encipher_vigenere(msg, key) 604 'QRGKKTHRZQEBPR' 605 606 Section 1 of the Kryptos sculpture at the CIA headquarters 607 uses this cipher and also changes the order of the the 608 alphabet [2]_. Here is the first line of that section of 609 the sculpture: 610 611 >>> from sympy.crypto.crypto import decipher_vigenere, padded_key 612 >>> alp = padded_key('KRYPTOS', AZ()) 613 >>> key = 'PALIMPSEST' 614 >>> msg = 'EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJ' 615 >>> decipher_vigenere(msg, key, alp) 616 'BETWEENSUBTLESHADINGANDTHEABSENC' 617 618 Explanation 619 =========== 620 621 The Vigenere cipher is named after Blaise de Vigenere, a sixteenth 622 century diplomat and cryptographer, by a historical accident. 623 Vigenere actually invented a different and more complicated cipher. 624 The so-called *Vigenere cipher* was actually invented 625 by Giovan Batista Belaso in 1553. 626 627 This cipher was used in the 1800's, for example, during the American 628 Civil War. The Confederacy used a brass cipher disk to implement the 629 Vigenere cipher (now on display in the NSA Museum in Fort 630 Meade) [1]_. 631 632 The Vigenere cipher is a generalization of the shift cipher. 633 Whereas the shift cipher shifts each letter by the same amount 634 (that amount being the key of the shift cipher) the Vigenere 635 cipher shifts a letter by an amount determined by the key (which is 636 a word or phrase known only to the sender and receiver). 637 638 For example, if the key was a single letter, such as "C", then the 639 so-called Vigenere cipher is actually a shift cipher with a 640 shift of `2` (since "C" is the 2nd letter of the alphabet, if 641 you start counting at `0`). If the key was a word with two 642 letters, such as "CA", then the so-called Vigenere cipher will 643 shift letters in even positions by `2` and letters in odd positions 644 are left alone (shifted by `0`, since "A" is the 0th letter, if 645 you start counting at `0`). 646 647 648 ALGORITHM: 649 650 INPUT: 651 652 ``msg``: string of characters that appear in ``symbols`` 653 (the plaintext) 654 655 ``key``: a string of characters that appear in ``symbols`` 656 (the secret key) 657 658 ``symbols``: a string of letters defining the alphabet 659 660 661 OUTPUT: 662 663 ``ct``: string of characters (the ciphertext message) 664 665 STEPS: 666 0. Number the letters of the alphabet from 0, ..., N 667 1. Compute from the string ``key`` a list ``L1`` of 668 corresponding integers. Let ``n1 = len(L1)``. 669 2. Compute from the string ``msg`` a list ``L2`` of 670 corresponding integers. Let ``n2 = len(L2)``. 671 3. Break ``L2`` up sequentially into sublists of size 672 ``n1``; the last sublist may be smaller than ``n1`` 673 4. For each of these sublists ``L`` of ``L2``, compute a 674 new list ``C`` given by ``C[i] = L[i] + L1[i] (mod N)`` 675 to the ``i``-th element in the sublist, for each ``i``. 676 5. Assemble these lists ``C`` by concatenation into a new 677 list of length ``n2``. 678 6. Compute from the new list a string ``ct`` of 679 corresponding letters. 680 681 Once it is known that the key is, say, `n` characters long, 682 frequency analysis can be applied to every `n`-th letter of 683 the ciphertext to determine the plaintext. This method is 684 called *Kasiski examination* (although it was first discovered 685 by Babbage). If they key is as long as the message and is 686 comprised of randomly selected characters -- a one-time pad -- the 687 message is theoretically unbreakable. 688 689 The cipher Vigenere actually discovered is an "auto-key" cipher 690 described as follows. 691 692 ALGORITHM: 693 694 INPUT: 695 696 ``key``: a string of letters (the secret key) 697 698 ``msg``: string of letters (the plaintext message) 699 700 OUTPUT: 701 702 ``ct``: string of upper-case letters (the ciphertext message) 703 704 STEPS: 705 0. Number the letters of the alphabet from 0, ..., N 706 1. Compute from the string ``msg`` a list ``L2`` of 707 corresponding integers. Let ``n2 = len(L2)``. 708 2. Let ``n1`` be the length of the key. Append to the 709 string ``key`` the first ``n2 - n1`` characters of 710 the plaintext message. Compute from this string (also of 711 length ``n2``) a list ``L1`` of integers corresponding 712 to the letter numbers in the first step. 713 3. Compute a new list ``C`` given by 714 ``C[i] = L1[i] + L2[i] (mod N)``. 715 4. Compute from the new list a string ``ct`` of letters 716 corresponding to the new integers. 717 718 To decipher the auto-key ciphertext, the key is used to decipher 719 the first ``n1`` characters and then those characters become the 720 key to decipher the next ``n1`` characters, etc...: 721 722 >>> m = AZ('go navy, beat army! yes you can'); m 723 'GONAVYBEATARMYYESYOUCAN' 724 >>> key = AZ('gold bug'); n1 = len(key); n2 = len(m) 725 >>> auto_key = key + m[:n2 - n1]; auto_key 726 'GOLDBUGGONAVYBEATARMYYE' 727 >>> ct = encipher_vigenere(m, auto_key); ct 728 'MCYDWSHKOGAMKZCELYFGAYR' 729 >>> n1 = len(key) 730 >>> pt = [] 731 >>> while ct: 732 ... part, ct = ct[:n1], ct[n1:] 733 ... pt.append(decipher_vigenere(part, key)) 734 ... key = pt[-1] 735 ... 736 >>> ''.join(pt) == m 737 True 738 739 References 740 ========== 741 742 .. [1] https://en.wikipedia.org/wiki/Vigenere_cipher 743 .. [2] http://web.archive.org/web/20071116100808/ 744 .. [3] http://filebox.vt.edu/users/batman/kryptos.html 745 (short URL: https://goo.gl/ijr22d) 746 747 """ 748 msg, key, A = _prep(msg, key, symbols) 749 map = {c: i for i, c in enumerate(A)} 750 key = [map[c] for c in key] 751 N = len(map) 752 k = len(key) 753 rv = [] 754 for i, m in enumerate(msg): 755 rv.append(A[(map[m] + key[i % k]) % N]) 756 rv = ''.join(rv) 757 return rv 758 759 760def decipher_vigenere(msg, key, symbols=None): 761 """ 762 Decode using the Vigenere cipher. 763 764 Examples 765 ======== 766 767 >>> from sympy.crypto.crypto import decipher_vigenere 768 >>> key = "encrypt" 769 >>> ct = "QRGK kt HRZQE BPR" 770 >>> decipher_vigenere(ct, key) 771 'MEETMEONMONDAY' 772 773 """ 774 msg, key, A = _prep(msg, key, symbols) 775 map = {c: i for i, c in enumerate(A)} 776 N = len(A) # normally, 26 777 K = [map[c] for c in key] 778 n = len(K) 779 C = [map[c] for c in msg] 780 rv = ''.join([A[(-K[i % n] + c) % N] for i, c in enumerate(C)]) 781 return rv 782 783 784#################### Hill cipher ######################## 785 786 787def encipher_hill(msg, key, symbols=None, pad="Q"): 788 r""" 789 Return the Hill cipher encryption of ``msg``. 790 791 Explanation 792 =========== 793 794 The Hill cipher [1]_, invented by Lester S. Hill in the 1920's [2]_, 795 was the first polygraphic cipher in which it was practical 796 (though barely) to operate on more than three symbols at once. 797 The following discussion assumes an elementary knowledge of 798 matrices. 799 800 First, each letter is first encoded as a number starting with 0. 801 Suppose your message `msg` consists of `n` capital letters, with no 802 spaces. This may be regarded an `n`-tuple M of elements of 803 `Z_{26}` (if the letters are those of the English alphabet). A key 804 in the Hill cipher is a `k x k` matrix `K`, all of whose entries 805 are in `Z_{26}`, such that the matrix `K` is invertible (i.e., the 806 linear transformation `K: Z_{N}^k \rightarrow Z_{N}^k` 807 is one-to-one). 808 809 810 Parameters 811 ========== 812 813 msg 814 Plaintext message of `n` upper-case letters. 815 816 key 817 A `k \times k` invertible matrix `K`, all of whose entries are 818 in `Z_{26}` (or whatever number of symbols are being used). 819 820 pad 821 Character (default "Q") to use to make length of text be a 822 multiple of ``k``. 823 824 Returns 825 ======= 826 827 ct 828 Ciphertext of upper-case letters. 829 830 Notes 831 ===== 832 833 ALGORITHM: 834 835 STEPS: 836 0. Number the letters of the alphabet from 0, ..., N 837 1. Compute from the string ``msg`` a list ``L`` of 838 corresponding integers. Let ``n = len(L)``. 839 2. Break the list ``L`` up into ``t = ceiling(n/k)`` 840 sublists ``L_1``, ..., ``L_t`` of size ``k`` (with 841 the last list "padded" to ensure its size is 842 ``k``). 843 3. Compute new list ``C_1``, ..., ``C_t`` given by 844 ``C[i] = K*L_i`` (arithmetic is done mod N), for each 845 ``i``. 846 4. Concatenate these into a list ``C = C_1 + ... + C_t``. 847 5. Compute from ``C`` a string ``ct`` of corresponding 848 letters. This has length ``k*t``. 849 850 References 851 ========== 852 853 .. [1] https://en.wikipedia.org/wiki/Hill_cipher 854 .. [2] Lester S. Hill, Cryptography in an Algebraic Alphabet, 855 The American Mathematical Monthly Vol.36, June-July 1929, 856 pp.306-312. 857 858 See Also 859 ======== 860 861 decipher_hill 862 863 """ 864 assert key.is_square 865 assert len(pad) == 1 866 msg, pad, A = _prep(msg, pad, symbols) 867 map = {c: i for i, c in enumerate(A)} 868 P = [map[c] for c in msg] 869 N = len(A) 870 k = key.cols 871 n = len(P) 872 m, r = divmod(n, k) 873 if r: 874 P = P + [map[pad]]*(k - r) 875 m += 1 876 rv = ''.join([A[c % N] for j in range(m) for c in 877 list(key*Matrix(k, 1, [P[i] 878 for i in range(k*j, k*(j + 1))]))]) 879 return rv 880 881 882def decipher_hill(msg, key, symbols=None): 883 """ 884 Deciphering is the same as enciphering but using the inverse of the 885 key matrix. 886 887 Examples 888 ======== 889 890 >>> from sympy.crypto.crypto import encipher_hill, decipher_hill 891 >>> from sympy import Matrix 892 893 >>> key = Matrix([[1, 2], [3, 5]]) 894 >>> encipher_hill("meet me on monday", key) 895 'UEQDUEODOCTCWQ' 896 >>> decipher_hill(_, key) 897 'MEETMEONMONDAY' 898 899 When the length of the plaintext (stripped of invalid characters) 900 is not a multiple of the key dimension, extra characters will 901 appear at the end of the enciphered and deciphered text. In order to 902 decipher the text, those characters must be included in the text to 903 be deciphered. In the following, the key has a dimension of 4 but 904 the text is 2 short of being a multiple of 4 so two characters will 905 be added. 906 907 >>> key = Matrix([[1, 1, 1, 2], [0, 1, 1, 0], 908 ... [2, 2, 3, 4], [1, 1, 0, 1]]) 909 >>> msg = "ST" 910 >>> encipher_hill(msg, key) 911 'HJEB' 912 >>> decipher_hill(_, key) 913 'STQQ' 914 >>> encipher_hill(msg, key, pad="Z") 915 'ISPK' 916 >>> decipher_hill(_, key) 917 'STZZ' 918 919 If the last two characters of the ciphertext were ignored in 920 either case, the wrong plaintext would be recovered: 921 922 >>> decipher_hill("HD", key) 923 'ORMV' 924 >>> decipher_hill("IS", key) 925 'UIKY' 926 927 See Also 928 ======== 929 930 encipher_hill 931 932 """ 933 assert key.is_square 934 msg, _, A = _prep(msg, '', symbols) 935 map = {c: i for i, c in enumerate(A)} 936 C = [map[c] for c in msg] 937 N = len(A) 938 k = key.cols 939 n = len(C) 940 m, r = divmod(n, k) 941 if r: 942 C = C + [0]*(k - r) 943 m += 1 944 key_inv = key.inv_mod(N) 945 rv = ''.join([A[p % N] for j in range(m) for p in 946 list(key_inv*Matrix( 947 k, 1, [C[i] for i in range(k*j, k*(j + 1))]))]) 948 return rv 949 950 951#################### Bifid cipher ######################## 952 953 954def encipher_bifid(msg, key, symbols=None): 955 r""" 956 Performs the Bifid cipher encryption on plaintext ``msg``, and 957 returns the ciphertext. 958 959 This is the version of the Bifid cipher that uses an `n \times n` 960 Polybius square. 961 962 Parameters 963 ========== 964 965 msg 966 Plaintext string. 967 968 key 969 Short string for key. 970 971 Duplicate characters are ignored and then it is padded with the 972 characters in ``symbols`` that were not in the short key. 973 974 symbols 975 `n \times n` characters defining the alphabet. 976 977 (default is string.printable) 978 979 Returns 980 ======= 981 982 ciphertext 983 Ciphertext using Bifid5 cipher without spaces. 984 985 See Also 986 ======== 987 988 decipher_bifid, encipher_bifid5, encipher_bifid6 989 990 References 991 ========== 992 993 .. [1] https://en.wikipedia.org/wiki/Bifid_cipher 994 995 """ 996 msg, key, A = _prep(msg, key, symbols, bifid10) 997 long_key = ''.join(uniq(key)) or A 998 999 n = len(A)**.5 1000 if n != int(n): 1001 raise ValueError( 1002 'Length of alphabet (%s) is not a square number.' % len(A)) 1003 N = int(n) 1004 if len(long_key) < N**2: 1005 long_key = list(long_key) + [x for x in A if x not in long_key] 1006 1007 # the fractionalization 1008 row_col = {ch: divmod(i, N) for i, ch in enumerate(long_key)} 1009 r, c = zip(*[row_col[x] for x in msg]) 1010 rc = r + c 1011 ch = {i: ch for ch, i in row_col.items()} 1012 rv = ''.join(ch[i] for i in zip(rc[::2], rc[1::2])) 1013 return rv 1014 1015 1016def decipher_bifid(msg, key, symbols=None): 1017 r""" 1018 Performs the Bifid cipher decryption on ciphertext ``msg``, and 1019 returns the plaintext. 1020 1021 This is the version of the Bifid cipher that uses the `n \times n` 1022 Polybius square. 1023 1024 Parameters 1025 ========== 1026 1027 msg 1028 Ciphertext string. 1029 1030 key 1031 Short string for key. 1032 1033 Duplicate characters are ignored and then it is padded with the 1034 characters in symbols that were not in the short key. 1035 1036 symbols 1037 `n \times n` characters defining the alphabet. 1038 1039 (default=string.printable, a `10 \times 10` matrix) 1040 1041 Returns 1042 ======= 1043 1044 deciphered 1045 Deciphered text. 1046 1047 Examples 1048 ======== 1049 1050 >>> from sympy.crypto.crypto import ( 1051 ... encipher_bifid, decipher_bifid, AZ) 1052 1053 Do an encryption using the bifid5 alphabet: 1054 1055 >>> alp = AZ().replace('J', '') 1056 >>> ct = AZ("meet me on monday!") 1057 >>> key = AZ("gold bug") 1058 >>> encipher_bifid(ct, key, alp) 1059 'IEILHHFSTSFQYE' 1060 1061 When entering the text or ciphertext, spaces are ignored so it 1062 can be formatted as desired. Re-entering the ciphertext from the 1063 preceding, putting 4 characters per line and padding with an extra 1064 J, does not cause problems for the deciphering: 1065 1066 >>> decipher_bifid(''' 1067 ... IEILH 1068 ... HFSTS 1069 ... FQYEJ''', key, alp) 1070 'MEETMEONMONDAY' 1071 1072 When no alphabet is given, all 100 printable characters will be 1073 used: 1074 1075 >>> key = '' 1076 >>> encipher_bifid('hello world!', key) 1077 'bmtwmg-bIo*w' 1078 >>> decipher_bifid(_, key) 1079 'hello world!' 1080 1081 If the key is changed, a different encryption is obtained: 1082 1083 >>> key = 'gold bug' 1084 >>> encipher_bifid('hello world!', 'gold_bug') 1085 'hg2sfuei7t}w' 1086 1087 And if the key used to decrypt the message is not exact, the 1088 original text will not be perfectly obtained: 1089 1090 >>> decipher_bifid(_, 'gold pug') 1091 'heldo~wor6d!' 1092 1093 """ 1094 msg, _, A = _prep(msg, '', symbols, bifid10) 1095 long_key = ''.join(uniq(key)) or A 1096 1097 n = len(A)**.5 1098 if n != int(n): 1099 raise ValueError( 1100 'Length of alphabet (%s) is not a square number.' % len(A)) 1101 N = int(n) 1102 if len(long_key) < N**2: 1103 long_key = list(long_key) + [x for x in A if x not in long_key] 1104 1105 # the reverse fractionalization 1106 row_col = { 1107 ch: divmod(i, N) for i, ch in enumerate(long_key)} 1108 rc = [i for c in msg for i in row_col[c]] 1109 n = len(msg) 1110 rc = zip(*(rc[:n], rc[n:])) 1111 ch = {i: ch for ch, i in row_col.items()} 1112 rv = ''.join(ch[i] for i in rc) 1113 return rv 1114 1115 1116def bifid_square(key): 1117 """Return characters of ``key`` arranged in a square. 1118 1119 Examples 1120 ======== 1121 1122 >>> from sympy.crypto.crypto import ( 1123 ... bifid_square, AZ, padded_key, bifid5) 1124 >>> bifid_square(AZ().replace('J', '')) 1125 Matrix([ 1126 [A, B, C, D, E], 1127 [F, G, H, I, K], 1128 [L, M, N, O, P], 1129 [Q, R, S, T, U], 1130 [V, W, X, Y, Z]]) 1131 1132 >>> bifid_square(padded_key(AZ('gold bug!'), bifid5)) 1133 Matrix([ 1134 [G, O, L, D, B], 1135 [U, A, C, E, F], 1136 [H, I, K, M, N], 1137 [P, Q, R, S, T], 1138 [V, W, X, Y, Z]]) 1139 1140 See Also 1141 ======== 1142 1143 padded_key 1144 1145 """ 1146 A = ''.join(uniq(''.join(key))) 1147 n = len(A)**.5 1148 if n != int(n): 1149 raise ValueError( 1150 'Length of alphabet (%s) is not a square number.' % len(A)) 1151 n = int(n) 1152 f = lambda i, j: Symbol(A[n*i + j]) 1153 rv = Matrix(n, n, f) 1154 return rv 1155 1156 1157def encipher_bifid5(msg, key): 1158 r""" 1159 Performs the Bifid cipher encryption on plaintext ``msg``, and 1160 returns the ciphertext. 1161 1162 Explanation 1163 =========== 1164 1165 This is the version of the Bifid cipher that uses the `5 \times 5` 1166 Polybius square. The letter "J" is ignored so it must be replaced 1167 with something else (traditionally an "I") before encryption. 1168 1169 ALGORITHM: (5x5 case) 1170 1171 STEPS: 1172 0. Create the `5 \times 5` Polybius square ``S`` associated 1173 to ``key`` as follows: 1174 1175 a) moving from left-to-right, top-to-bottom, 1176 place the letters of the key into a `5 \times 5` 1177 matrix, 1178 b) if the key has less than 25 letters, add the 1179 letters of the alphabet not in the key until the 1180 `5 \times 5` square is filled. 1181 1182 1. Create a list ``P`` of pairs of numbers which are the 1183 coordinates in the Polybius square of the letters in 1184 ``msg``. 1185 2. Let ``L1`` be the list of all first coordinates of ``P`` 1186 (length of ``L1 = n``), let ``L2`` be the list of all 1187 second coordinates of ``P`` (so the length of ``L2`` 1188 is also ``n``). 1189 3. Let ``L`` be the concatenation of ``L1`` and ``L2`` 1190 (length ``L = 2*n``), except that consecutive numbers 1191 are paired ``(L[2*i], L[2*i + 1])``. You can regard 1192 ``L`` as a list of pairs of length ``n``. 1193 4. Let ``C`` be the list of all letters which are of the 1194 form ``S[i, j]``, for all ``(i, j)`` in ``L``. As a 1195 string, this is the ciphertext of ``msg``. 1196 1197 Parameters 1198 ========== 1199 1200 msg : str 1201 Plaintext string. 1202 1203 Converted to upper case and filtered of anything but all letters 1204 except J. 1205 1206 key 1207 Short string for key; non-alphabetic letters, J and duplicated 1208 characters are ignored and then, if the length is less than 25 1209 characters, it is padded with other letters of the alphabet 1210 (in alphabetical order). 1211 1212 Returns 1213 ======= 1214 1215 ct 1216 Ciphertext (all caps, no spaces). 1217 1218 Examples 1219 ======== 1220 1221 >>> from sympy.crypto.crypto import ( 1222 ... encipher_bifid5, decipher_bifid5) 1223 1224 "J" will be omitted unless it is replaced with something else: 1225 1226 >>> round_trip = lambda m, k: \ 1227 ... decipher_bifid5(encipher_bifid5(m, k), k) 1228 >>> key = 'a' 1229 >>> msg = "JOSIE" 1230 >>> round_trip(msg, key) 1231 'OSIE' 1232 >>> round_trip(msg.replace("J", "I"), key) 1233 'IOSIE' 1234 >>> j = "QIQ" 1235 >>> round_trip(msg.replace("J", j), key).replace(j, "J") 1236 'JOSIE' 1237 1238 1239 Notes 1240 ===== 1241 1242 The Bifid cipher was invented around 1901 by Felix Delastelle. 1243 It is a *fractional substitution* cipher, where letters are 1244 replaced by pairs of symbols from a smaller alphabet. The 1245 cipher uses a `5 \times 5` square filled with some ordering of the 1246 alphabet, except that "J" is replaced with "I" (this is a so-called 1247 Polybius square; there is a `6 \times 6` analog if you add back in 1248 "J" and also append onto the usual 26 letter alphabet, the digits 1249 0, 1, ..., 9). 1250 According to Helen Gaines' book *Cryptanalysis*, this type of cipher 1251 was used in the field by the German Army during World War I. 1252 1253 See Also 1254 ======== 1255 1256 decipher_bifid5, encipher_bifid 1257 1258 """ 1259 msg, key, _ = _prep(msg.upper(), key.upper(), None, bifid5) 1260 key = padded_key(key, bifid5) 1261 return encipher_bifid(msg, '', key) 1262 1263 1264def decipher_bifid5(msg, key): 1265 r""" 1266 Return the Bifid cipher decryption of ``msg``. 1267 1268 Explanation 1269 =========== 1270 1271 This is the version of the Bifid cipher that uses the `5 \times 5` 1272 Polybius square; the letter "J" is ignored unless a ``key`` of 1273 length 25 is used. 1274 1275 Parameters 1276 ========== 1277 1278 msg 1279 Ciphertext string. 1280 1281 key 1282 Short string for key; duplicated characters are ignored and if 1283 the length is less then 25 characters, it will be padded with 1284 other letters from the alphabet omitting "J". 1285 Non-alphabetic characters are ignored. 1286 1287 Returns 1288 ======= 1289 1290 plaintext 1291 Plaintext from Bifid5 cipher (all caps, no spaces). 1292 1293 Examples 1294 ======== 1295 1296 >>> from sympy.crypto.crypto import encipher_bifid5, decipher_bifid5 1297 >>> key = "gold bug" 1298 >>> encipher_bifid5('meet me on friday', key) 1299 'IEILEHFSTSFXEE' 1300 >>> encipher_bifid5('meet me on monday', key) 1301 'IEILHHFSTSFQYE' 1302 >>> decipher_bifid5(_, key) 1303 'MEETMEONMONDAY' 1304 1305 """ 1306 msg, key, _ = _prep(msg.upper(), key.upper(), None, bifid5) 1307 key = padded_key(key, bifid5) 1308 return decipher_bifid(msg, '', key) 1309 1310 1311def bifid5_square(key=None): 1312 r""" 1313 5x5 Polybius square. 1314 1315 Produce the Polybius square for the `5 \times 5` Bifid cipher. 1316 1317 Examples 1318 ======== 1319 1320 >>> from sympy.crypto.crypto import bifid5_square 1321 >>> bifid5_square("gold bug") 1322 Matrix([ 1323 [G, O, L, D, B], 1324 [U, A, C, E, F], 1325 [H, I, K, M, N], 1326 [P, Q, R, S, T], 1327 [V, W, X, Y, Z]]) 1328 1329 """ 1330 if not key: 1331 key = bifid5 1332 else: 1333 _, key, _ = _prep('', key.upper(), None, bifid5) 1334 key = padded_key(key, bifid5) 1335 return bifid_square(key) 1336 1337 1338def encipher_bifid6(msg, key): 1339 r""" 1340 Performs the Bifid cipher encryption on plaintext ``msg``, and 1341 returns the ciphertext. 1342 1343 This is the version of the Bifid cipher that uses the `6 \times 6` 1344 Polybius square. 1345 1346 Parameters 1347 ========== 1348 1349 msg 1350 Plaintext string (digits okay). 1351 1352 key 1353 Short string for key (digits okay). 1354 1355 If ``key`` is less than 36 characters long, the square will be 1356 filled with letters A through Z and digits 0 through 9. 1357 1358 Returns 1359 ======= 1360 1361 ciphertext 1362 Ciphertext from Bifid cipher (all caps, no spaces). 1363 1364 See Also 1365 ======== 1366 1367 decipher_bifid6, encipher_bifid 1368 1369 """ 1370 msg, key, _ = _prep(msg.upper(), key.upper(), None, bifid6) 1371 key = padded_key(key, bifid6) 1372 return encipher_bifid(msg, '', key) 1373 1374 1375def decipher_bifid6(msg, key): 1376 r""" 1377 Performs the Bifid cipher decryption on ciphertext ``msg``, and 1378 returns the plaintext. 1379 1380 This is the version of the Bifid cipher that uses the `6 \times 6` 1381 Polybius square. 1382 1383 Parameters 1384 ========== 1385 1386 msg 1387 Ciphertext string (digits okay); converted to upper case 1388 1389 key 1390 Short string for key (digits okay). 1391 1392 If ``key`` is less than 36 characters long, the square will be 1393 filled with letters A through Z and digits 0 through 9. 1394 All letters are converted to uppercase. 1395 1396 Returns 1397 ======= 1398 1399 plaintext 1400 Plaintext from Bifid cipher (all caps, no spaces). 1401 1402 Examples 1403 ======== 1404 1405 >>> from sympy.crypto.crypto import encipher_bifid6, decipher_bifid6 1406 >>> key = "gold bug" 1407 >>> encipher_bifid6('meet me on monday at 8am', key) 1408 'KFKLJJHF5MMMKTFRGPL' 1409 >>> decipher_bifid6(_, key) 1410 'MEETMEONMONDAYAT8AM' 1411 1412 """ 1413 msg, key, _ = _prep(msg.upper(), key.upper(), None, bifid6) 1414 key = padded_key(key, bifid6) 1415 return decipher_bifid(msg, '', key) 1416 1417 1418def bifid6_square(key=None): 1419 r""" 1420 6x6 Polybius square. 1421 1422 Produces the Polybius square for the `6 \times 6` Bifid cipher. 1423 Assumes alphabet of symbols is "A", ..., "Z", "0", ..., "9". 1424 1425 Examples 1426 ======== 1427 1428 >>> from sympy.crypto.crypto import bifid6_square 1429 >>> key = "gold bug" 1430 >>> bifid6_square(key) 1431 Matrix([ 1432 [G, O, L, D, B, U], 1433 [A, C, E, F, H, I], 1434 [J, K, M, N, P, Q], 1435 [R, S, T, V, W, X], 1436 [Y, Z, 0, 1, 2, 3], 1437 [4, 5, 6, 7, 8, 9]]) 1438 1439 """ 1440 if not key: 1441 key = bifid6 1442 else: 1443 _, key, _ = _prep('', key.upper(), None, bifid6) 1444 key = padded_key(key, bifid6) 1445 return bifid_square(key) 1446 1447 1448#################### RSA ############################# 1449 1450def _decipher_rsa_crt(i, d, factors): 1451 """Decipher RSA using chinese remainder theorem from the information 1452 of the relatively-prime factors of the modulus. 1453 1454 Parameters 1455 ========== 1456 1457 i : integer 1458 Ciphertext 1459 1460 d : integer 1461 The exponent component. 1462 1463 factors : list of relatively-prime integers 1464 The integers given must be coprime and the product must equal 1465 the modulus component of the original RSA key. 1466 1467 Examples 1468 ======== 1469 1470 How to decrypt RSA with CRT: 1471 1472 >>> from sympy.crypto.crypto import rsa_public_key, rsa_private_key 1473 >>> primes = [61, 53] 1474 >>> e = 17 1475 >>> args = primes + [e] 1476 >>> puk = rsa_public_key(*args) 1477 >>> prk = rsa_private_key(*args) 1478 1479 >>> from sympy.crypto.crypto import encipher_rsa, _decipher_rsa_crt 1480 >>> msg = 65 1481 >>> crt_primes = primes 1482 >>> encrypted = encipher_rsa(msg, puk) 1483 >>> decrypted = _decipher_rsa_crt(encrypted, prk[1], primes) 1484 >>> decrypted 1485 65 1486 """ 1487 from sympy.ntheory.modular import crt 1488 moduluses = [pow(i, d, p) for p in factors] 1489 1490 result = crt(factors, moduluses) 1491 if not result: 1492 raise ValueError("CRT failed") 1493 return result[0] 1494 1495 1496def _rsa_key(*args, public=True, private=True, totient='Euler', index=None, multipower=None): 1497 r"""A private subroutine to generate RSA key 1498 1499 Parameters 1500 ========== 1501 1502 public, private : bool, optional 1503 Flag to generate either a public key, a private key. 1504 1505 totient : 'Euler' or 'Carmichael' 1506 Different notation used for totient. 1507 1508 multipower : bool, optional 1509 Flag to bypass warning for multipower RSA. 1510 """ 1511 from sympy.ntheory import totient as _euler 1512 from sympy.ntheory import reduced_totient as _carmichael 1513 1514 if len(args) < 2: 1515 return False 1516 1517 if totient not in ('Euler', 'Carmichael'): 1518 raise ValueError( 1519 "The argument totient={} should either be " \ 1520 "'Euler', 'Carmichalel'." \ 1521 .format(totient)) 1522 1523 if totient == 'Euler': 1524 _totient = _euler 1525 else: 1526 _totient = _carmichael 1527 1528 if index is not None: 1529 index = as_int(index) 1530 if totient != 'Carmichael': 1531 raise ValueError( 1532 "Setting the 'index' keyword argument requires totient" 1533 "notation to be specified as 'Carmichael'.") 1534 1535 primes, e = args[:-1], args[-1] 1536 1537 if any(not isprime(p) for p in primes): 1538 new_primes = [] 1539 for i in primes: 1540 new_primes.extend(factorint(i, multiple=True)) 1541 primes = new_primes 1542 1543 n = reduce(lambda i, j: i*j, primes) 1544 1545 tally = multiset(primes) 1546 if all(v == 1 for v in tally.values()): 1547 multiple = list(tally.keys()) 1548 phi = _totient._from_distinct_primes(*multiple) 1549 1550 else: 1551 if not multipower: 1552 NonInvertibleCipherWarning( 1553 'Non-distinctive primes found in the factors {}. ' 1554 'The cipher may not be decryptable for some numbers ' 1555 'in the complete residue system Z[{}], but the cipher ' 1556 'can still be valid if you restrict the domain to be ' 1557 'the reduced residue system Z*[{}]. You can pass ' 1558 'the flag multipower=True if you want to suppress this ' 1559 'warning.' 1560 .format(primes, n, n) 1561 ).warn() 1562 phi = _totient._from_factors(tally) 1563 1564 if igcd(e, phi) == 1: 1565 if public and not private: 1566 if isinstance(index, int): 1567 e = e % phi 1568 e += index * phi 1569 return n, e 1570 1571 if private and not public: 1572 d = mod_inverse(e, phi) 1573 if isinstance(index, int): 1574 d += index * phi 1575 return n, d 1576 1577 return False 1578 1579 1580def rsa_public_key(*args, **kwargs): 1581 r"""Return the RSA *public key* pair, `(n, e)` 1582 1583 Parameters 1584 ========== 1585 1586 args : naturals 1587 If specified as `p, q, e` where `p` and `q` are distinct primes 1588 and `e` is a desired public exponent of the RSA, `n = p q` and 1589 `e` will be verified against the totient 1590 `\phi(n)` (Euler totient) or `\lambda(n)` (Carmichael totient) 1591 to be `\gcd(e, \phi(n)) = 1` or `\gcd(e, \lambda(n)) = 1`. 1592 1593 If specified as `p_1, p_2, ..., p_n, e` where 1594 `p_1, p_2, ..., p_n` are specified as primes, 1595 and `e` is specified as a desired public exponent of the RSA, 1596 it will be able to form a multi-prime RSA, which is a more 1597 generalized form of the popular 2-prime RSA. 1598 1599 It can also be possible to form a single-prime RSA by specifying 1600 the argument as `p, e`, which can be considered a trivial case 1601 of a multiprime RSA. 1602 1603 Furthermore, it can be possible to form a multi-power RSA by 1604 specifying two or more pairs of the primes to be same. 1605 However, unlike the two-distinct prime RSA or multi-prime 1606 RSA, not every numbers in the complete residue system 1607 (`\mathbb{Z}_n`) will be decryptable since the mapping 1608 `\mathbb{Z}_{n} \rightarrow \mathbb{Z}_{n}` 1609 will not be bijective. 1610 (Only except for the trivial case when 1611 `e = 1` 1612 or more generally, 1613 1614 .. math:: 1615 e \in \left \{ 1 + k \lambda(n) 1616 \mid k \in \mathbb{Z} \land k \geq 0 \right \} 1617 1618 when RSA reduces to the identity.) 1619 However, the RSA can still be decryptable for the numbers in the 1620 reduced residue system (`\mathbb{Z}_n^{\times}`), since the 1621 mapping 1622 `\mathbb{Z}_{n}^{\times} \rightarrow \mathbb{Z}_{n}^{\times}` 1623 can still be bijective. 1624 1625 If you pass a non-prime integer to the arguments 1626 `p_1, p_2, ..., p_n`, the particular number will be 1627 prime-factored and it will become either a multi-prime RSA or a 1628 multi-power RSA in its canonical form, depending on whether the 1629 product equals its radical or not. 1630 `p_1 p_2 ... p_n = \text{rad}(p_1 p_2 ... p_n)` 1631 1632 totient : bool, optional 1633 If ``'Euler'``, it uses Euler's totient `\phi(n)` which is 1634 :meth:`sympy.ntheory.factor_.totient` in SymPy. 1635 1636 If ``'Carmichael'``, it uses Carmichael's totient `\lambda(n)` 1637 which is :meth:`sympy.ntheory.factor_.reduced_totient` in SymPy. 1638 1639 Unlike private key generation, this is a trivial keyword for 1640 public key generation because 1641 `\gcd(e, \phi(n)) = 1 \iff \gcd(e, \lambda(n)) = 1`. 1642 1643 index : nonnegative integer, optional 1644 Returns an arbitrary solution of a RSA public key at the index 1645 specified at `0, 1, 2, ...`. This parameter needs to be 1646 specified along with ``totient='Carmichael'``. 1647 1648 Similarly to the non-uniquenss of a RSA private key as described 1649 in the ``index`` parameter documentation in 1650 :meth:`rsa_private_key`, RSA public key is also not unique and 1651 there is an infinite number of RSA public exponents which 1652 can behave in the same manner. 1653 1654 From any given RSA public exponent `e`, there are can be an 1655 another RSA public exponent `e + k \lambda(n)` where `k` is an 1656 integer, `\lambda` is a Carmichael's totient function. 1657 1658 However, considering only the positive cases, there can be 1659 a principal solution of a RSA public exponent `e_0` in 1660 `0 < e_0 < \lambda(n)`, and all the other solutions 1661 can be canonicalzed in a form of `e_0 + k \lambda(n)`. 1662 1663 ``index`` specifies the `k` notation to yield any possible value 1664 an RSA public key can have. 1665 1666 An example of computing any arbitrary RSA public key: 1667 1668 >>> from sympy.crypto.crypto import rsa_public_key 1669 >>> rsa_public_key(61, 53, 17, totient='Carmichael', index=0) 1670 (3233, 17) 1671 >>> rsa_public_key(61, 53, 17, totient='Carmichael', index=1) 1672 (3233, 797) 1673 >>> rsa_public_key(61, 53, 17, totient='Carmichael', index=2) 1674 (3233, 1577) 1675 1676 multipower : bool, optional 1677 Any pair of non-distinct primes found in the RSA specification 1678 will restrict the domain of the cryptosystem, as noted in the 1679 explaination of the parameter ``args``. 1680 1681 SymPy RSA key generator may give a warning before dispatching it 1682 as a multi-power RSA, however, you can disable the warning if 1683 you pass ``True`` to this keyword. 1684 1685 Returns 1686 ======= 1687 1688 (n, e) : int, int 1689 `n` is a product of any arbitrary number of primes given as 1690 the argument. 1691 1692 `e` is relatively prime (coprime) to the Euler totient 1693 `\phi(n)`. 1694 1695 False 1696 Returned if less than two arguments are given, or `e` is 1697 not relatively prime to the modulus. 1698 1699 Examples 1700 ======== 1701 1702 >>> from sympy.crypto.crypto import rsa_public_key 1703 1704 A public key of a two-prime RSA: 1705 1706 >>> p, q, e = 3, 5, 7 1707 >>> rsa_public_key(p, q, e) 1708 (15, 7) 1709 >>> rsa_public_key(p, q, 30) 1710 False 1711 1712 A public key of a multiprime RSA: 1713 1714 >>> primes = [2, 3, 5, 7, 11, 13] 1715 >>> e = 7 1716 >>> args = primes + [e] 1717 >>> rsa_public_key(*args) 1718 (30030, 7) 1719 1720 Notes 1721 ===== 1722 1723 Although the RSA can be generalized over any modulus `n`, using 1724 two large primes had became the most popular specification because a 1725 product of two large primes is usually the hardest to factor 1726 relatively to the digits of `n` can have. 1727 1728 However, it may need further understanding of the time complexities 1729 of each prime-factoring algorithms to verify the claim. 1730 1731 See Also 1732 ======== 1733 1734 rsa_private_key 1735 encipher_rsa 1736 decipher_rsa 1737 1738 References 1739 ========== 1740 1741 .. [1] https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29 1742 1743 .. [2] http://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf 1744 1745 .. [3] https://link.springer.com/content/pdf/10.1007%2FBFb0055738.pdf 1746 1747 .. [4] http://www.itiis.org/digital-library/manuscript/1381 1748 """ 1749 return _rsa_key(*args, public=True, private=False, **kwargs) 1750 1751 1752def rsa_private_key(*args, **kwargs): 1753 r"""Return the RSA *private key* pair, `(n, d)` 1754 1755 Parameters 1756 ========== 1757 1758 args : naturals 1759 The keyword is identical to the ``args`` in 1760 :meth:`rsa_public_key`. 1761 1762 totient : bool, optional 1763 If ``'Euler'``, it uses Euler's totient convention `\phi(n)` 1764 which is :meth:`sympy.ntheory.factor_.totient` in SymPy. 1765 1766 If ``'Carmichael'``, it uses Carmichael's totient convention 1767 `\lambda(n)` which is 1768 :meth:`sympy.ntheory.factor_.reduced_totient` in SymPy. 1769 1770 There can be some output differences for private key generation 1771 as examples below. 1772 1773 Example using Euler's totient: 1774 1775 >>> from sympy.crypto.crypto import rsa_private_key 1776 >>> rsa_private_key(61, 53, 17, totient='Euler') 1777 (3233, 2753) 1778 1779 Example using Carmichael's totient: 1780 1781 >>> from sympy.crypto.crypto import rsa_private_key 1782 >>> rsa_private_key(61, 53, 17, totient='Carmichael') 1783 (3233, 413) 1784 1785 index : nonnegative integer, optional 1786 Returns an arbitrary solution of a RSA private key at the index 1787 specified at `0, 1, 2, ...`. This parameter needs to be 1788 specified along with ``totient='Carmichael'``. 1789 1790 RSA private exponent is a non-unique solution of 1791 `e d \mod \lambda(n) = 1` and it is possible in any form of 1792 `d + k \lambda(n)`, where `d` is an another 1793 already-computed private exponent, and `\lambda` is a 1794 Carmichael's totient function, and `k` is any integer. 1795 1796 However, considering only the positive cases, there can be 1797 a principal solution of a RSA private exponent `d_0` in 1798 `0 < d_0 < \lambda(n)`, and all the other solutions 1799 can be canonicalzed in a form of `d_0 + k \lambda(n)`. 1800 1801 ``index`` specifies the `k` notation to yield any possible value 1802 an RSA private key can have. 1803 1804 An example of computing any arbitrary RSA private key: 1805 1806 >>> from sympy.crypto.crypto import rsa_private_key 1807 >>> rsa_private_key(61, 53, 17, totient='Carmichael', index=0) 1808 (3233, 413) 1809 >>> rsa_private_key(61, 53, 17, totient='Carmichael', index=1) 1810 (3233, 1193) 1811 >>> rsa_private_key(61, 53, 17, totient='Carmichael', index=2) 1812 (3233, 1973) 1813 1814 multipower : bool, optional 1815 The keyword is identical to the ``multipower`` in 1816 :meth:`rsa_public_key`. 1817 1818 Returns 1819 ======= 1820 1821 (n, d) : int, int 1822 `n` is a product of any arbitrary number of primes given as 1823 the argument. 1824 1825 `d` is the inverse of `e` (mod `\phi(n)`) where `e` is the 1826 exponent given, and `\phi` is a Euler totient. 1827 1828 False 1829 Returned if less than two arguments are given, or `e` is 1830 not relatively prime to the totient of the modulus. 1831 1832 Examples 1833 ======== 1834 1835 >>> from sympy.crypto.crypto import rsa_private_key 1836 1837 A private key of a two-prime RSA: 1838 1839 >>> p, q, e = 3, 5, 7 1840 >>> rsa_private_key(p, q, e) 1841 (15, 7) 1842 >>> rsa_private_key(p, q, 30) 1843 False 1844 1845 A private key of a multiprime RSA: 1846 1847 >>> primes = [2, 3, 5, 7, 11, 13] 1848 >>> e = 7 1849 >>> args = primes + [e] 1850 >>> rsa_private_key(*args) 1851 (30030, 823) 1852 1853 See Also 1854 ======== 1855 1856 rsa_public_key 1857 encipher_rsa 1858 decipher_rsa 1859 1860 References 1861 ========== 1862 1863 .. [1] https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29 1864 1865 .. [2] http://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf 1866 1867 .. [3] https://link.springer.com/content/pdf/10.1007%2FBFb0055738.pdf 1868 1869 .. [4] http://www.itiis.org/digital-library/manuscript/1381 1870 """ 1871 return _rsa_key(*args, public=False, private=True, **kwargs) 1872 1873 1874def _encipher_decipher_rsa(i, key, factors=None): 1875 n, d = key 1876 if not factors: 1877 return pow(i, d, n) 1878 1879 def _is_coprime_set(l): 1880 is_coprime_set = True 1881 for i in range(len(l)): 1882 for j in range(i+1, len(l)): 1883 if igcd(l[i], l[j]) != 1: 1884 is_coprime_set = False 1885 break 1886 return is_coprime_set 1887 1888 prod = reduce(lambda i, j: i*j, factors) 1889 if prod == n and _is_coprime_set(factors): 1890 return _decipher_rsa_crt(i, d, factors) 1891 return _encipher_decipher_rsa(i, key, factors=None) 1892 1893 1894def encipher_rsa(i, key, factors=None): 1895 r"""Encrypt the plaintext with RSA. 1896 1897 Parameters 1898 ========== 1899 1900 i : integer 1901 The plaintext to be encrypted for. 1902 1903 key : (n, e) where n, e are integers 1904 `n` is the modulus of the key and `e` is the exponent of the 1905 key. The encryption is computed by `i^e \bmod n`. 1906 1907 The key can either be a public key or a private key, however, 1908 the message encrypted by a public key can only be decrypted by 1909 a private key, and vice versa, as RSA is an asymmetric 1910 cryptography system. 1911 1912 factors : list of coprime integers 1913 This is identical to the keyword ``factors`` in 1914 :meth:`decipher_rsa`. 1915 1916 Notes 1917 ===== 1918 1919 Some specifications may make the RSA not cryptographically 1920 meaningful. 1921 1922 For example, `0`, `1` will remain always same after taking any 1923 number of exponentiation, thus, should be avoided. 1924 1925 Furthermore, if `i^e < n`, `i` may easily be figured out by taking 1926 `e` th root. 1927 1928 And also, specifying the exponent as `1` or in more generalized form 1929 as `1 + k \lambda(n)` where `k` is an nonnegative integer, 1930 `\lambda` is a carmichael totient, the RSA becomes an identity 1931 mapping. 1932 1933 Examples 1934 ======== 1935 1936 >>> from sympy.crypto.crypto import encipher_rsa 1937 >>> from sympy.crypto.crypto import rsa_public_key, rsa_private_key 1938 1939 Public Key Encryption: 1940 1941 >>> p, q, e = 3, 5, 7 1942 >>> puk = rsa_public_key(p, q, e) 1943 >>> msg = 12 1944 >>> encipher_rsa(msg, puk) 1945 3 1946 1947 Private Key Encryption: 1948 1949 >>> p, q, e = 3, 5, 7 1950 >>> prk = rsa_private_key(p, q, e) 1951 >>> msg = 12 1952 >>> encipher_rsa(msg, prk) 1953 3 1954 1955 Encryption using chinese remainder theorem: 1956 1957 >>> encipher_rsa(msg, prk, factors=[p, q]) 1958 3 1959 """ 1960 return _encipher_decipher_rsa(i, key, factors=factors) 1961 1962 1963def decipher_rsa(i, key, factors=None): 1964 r"""Decrypt the ciphertext with RSA. 1965 1966 Parameters 1967 ========== 1968 1969 i : integer 1970 The ciphertext to be decrypted for. 1971 1972 key : (n, d) where n, d are integers 1973 `n` is the modulus of the key and `d` is the exponent of the 1974 key. The decryption is computed by `i^d \bmod n`. 1975 1976 The key can either be a public key or a private key, however, 1977 the message encrypted by a public key can only be decrypted by 1978 a private key, and vice versa, as RSA is an asymmetric 1979 cryptography system. 1980 1981 factors : list of coprime integers 1982 As the modulus `n` created from RSA key generation is composed 1983 of arbitrary prime factors 1984 `n = {p_1}^{k_1}{p_2}^{k_2}...{p_n}^{k_n}` where 1985 `p_1, p_2, ..., p_n` are distinct primes and 1986 `k_1, k_2, ..., k_n` are positive integers, chinese remainder 1987 theorem can be used to compute `i^d \bmod n` from the 1988 fragmented modulo operations like 1989 1990 .. math:: 1991 i^d \bmod {p_1}^{k_1}, i^d \bmod {p_2}^{k_2}, ... , 1992 i^d \bmod {p_n}^{k_n} 1993 1994 or like 1995 1996 .. math:: 1997 i^d \bmod {p_1}^{k_1}{p_2}^{k_2}, 1998 i^d \bmod {p_3}^{k_3}, ... , 1999 i^d \bmod {p_n}^{k_n} 2000 2001 as long as every moduli does not share any common divisor each 2002 other. 2003 2004 The raw primes used in generating the RSA key pair can be a good 2005 option. 2006 2007 Note that the speed advantage of using this is only viable for 2008 very large cases (Like 2048-bit RSA keys) since the 2009 overhead of using pure python implementation of 2010 :meth:`sympy.ntheory.modular.crt` may overcompensate the 2011 theoritical speed advantage. 2012 2013 Notes 2014 ===== 2015 2016 See the ``Notes`` section in the documentation of 2017 :meth:`encipher_rsa` 2018 2019 Examples 2020 ======== 2021 2022 >>> from sympy.crypto.crypto import decipher_rsa, encipher_rsa 2023 >>> from sympy.crypto.crypto import rsa_public_key, rsa_private_key 2024 2025 Public Key Encryption and Decryption: 2026 2027 >>> p, q, e = 3, 5, 7 2028 >>> prk = rsa_private_key(p, q, e) 2029 >>> puk = rsa_public_key(p, q, e) 2030 >>> msg = 12 2031 >>> new_msg = encipher_rsa(msg, prk) 2032 >>> new_msg 2033 3 2034 >>> decipher_rsa(new_msg, puk) 2035 12 2036 2037 Private Key Encryption and Decryption: 2038 2039 >>> p, q, e = 3, 5, 7 2040 >>> prk = rsa_private_key(p, q, e) 2041 >>> puk = rsa_public_key(p, q, e) 2042 >>> msg = 12 2043 >>> new_msg = encipher_rsa(msg, puk) 2044 >>> new_msg 2045 3 2046 >>> decipher_rsa(new_msg, prk) 2047 12 2048 2049 Decryption using chinese remainder theorem: 2050 2051 >>> decipher_rsa(new_msg, prk, factors=[p, q]) 2052 12 2053 2054 See Also 2055 ======== 2056 2057 encipher_rsa 2058 """ 2059 return _encipher_decipher_rsa(i, key, factors=factors) 2060 2061 2062#################### kid krypto (kid RSA) ############################# 2063 2064 2065def kid_rsa_public_key(a, b, A, B): 2066 r""" 2067 Kid RSA is a version of RSA useful to teach grade school children 2068 since it does not involve exponentiation. 2069 2070 Explanation 2071 =========== 2072 2073 Alice wants to talk to Bob. Bob generates keys as follows. 2074 Key generation: 2075 2076 * Select positive integers `a, b, A, B` at random. 2077 * Compute `M = a b - 1`, `e = A M + a`, `d = B M + b`, 2078 `n = (e d - 1)//M`. 2079 * The *public key* is `(n, e)`. Bob sends these to Alice. 2080 * The *private key* is `(n, d)`, which Bob keeps secret. 2081 2082 Encryption: If `p` is the plaintext message then the 2083 ciphertext is `c = p e \pmod n`. 2084 2085 Decryption: If `c` is the ciphertext message then the 2086 plaintext is `p = c d \pmod n`. 2087 2088 Examples 2089 ======== 2090 2091 >>> from sympy.crypto.crypto import kid_rsa_public_key 2092 >>> a, b, A, B = 3, 4, 5, 6 2093 >>> kid_rsa_public_key(a, b, A, B) 2094 (369, 58) 2095 2096 """ 2097 M = a*b - 1 2098 e = A*M + a 2099 d = B*M + b 2100 n = (e*d - 1)//M 2101 return n, e 2102 2103 2104def kid_rsa_private_key(a, b, A, B): 2105 """ 2106 Compute `M = a b - 1`, `e = A M + a`, `d = B M + b`, 2107 `n = (e d - 1) / M`. The *private key* is `d`, which Bob 2108 keeps secret. 2109 2110 Examples 2111 ======== 2112 2113 >>> from sympy.crypto.crypto import kid_rsa_private_key 2114 >>> a, b, A, B = 3, 4, 5, 6 2115 >>> kid_rsa_private_key(a, b, A, B) 2116 (369, 70) 2117 2118 """ 2119 M = a*b - 1 2120 e = A*M + a 2121 d = B*M + b 2122 n = (e*d - 1)//M 2123 return n, d 2124 2125 2126def encipher_kid_rsa(msg, key): 2127 """ 2128 Here ``msg`` is the plaintext and ``key`` is the public key. 2129 2130 Examples 2131 ======== 2132 2133 >>> from sympy.crypto.crypto import ( 2134 ... encipher_kid_rsa, kid_rsa_public_key) 2135 >>> msg = 200 2136 >>> a, b, A, B = 3, 4, 5, 6 2137 >>> key = kid_rsa_public_key(a, b, A, B) 2138 >>> encipher_kid_rsa(msg, key) 2139 161 2140 2141 """ 2142 n, e = key 2143 return (msg*e) % n 2144 2145 2146def decipher_kid_rsa(msg, key): 2147 """ 2148 Here ``msg`` is the plaintext and ``key`` is the private key. 2149 2150 Examples 2151 ======== 2152 2153 >>> from sympy.crypto.crypto import ( 2154 ... kid_rsa_public_key, kid_rsa_private_key, 2155 ... decipher_kid_rsa, encipher_kid_rsa) 2156 >>> a, b, A, B = 3, 4, 5, 6 2157 >>> d = kid_rsa_private_key(a, b, A, B) 2158 >>> msg = 200 2159 >>> pub = kid_rsa_public_key(a, b, A, B) 2160 >>> pri = kid_rsa_private_key(a, b, A, B) 2161 >>> ct = encipher_kid_rsa(msg, pub) 2162 >>> decipher_kid_rsa(ct, pri) 2163 200 2164 2165 """ 2166 n, d = key 2167 return (msg*d) % n 2168 2169 2170#################### Morse Code ###################################### 2171 2172morse_char = { 2173 ".-": "A", "-...": "B", 2174 "-.-.": "C", "-..": "D", 2175 ".": "E", "..-.": "F", 2176 "--.": "G", "....": "H", 2177 "..": "I", ".---": "J", 2178 "-.-": "K", ".-..": "L", 2179 "--": "M", "-.": "N", 2180 "---": "O", ".--.": "P", 2181 "--.-": "Q", ".-.": "R", 2182 "...": "S", "-": "T", 2183 "..-": "U", "...-": "V", 2184 ".--": "W", "-..-": "X", 2185 "-.--": "Y", "--..": "Z", 2186 "-----": "0", ".----": "1", 2187 "..---": "2", "...--": "3", 2188 "....-": "4", ".....": "5", 2189 "-....": "6", "--...": "7", 2190 "---..": "8", "----.": "9", 2191 ".-.-.-": ".", "--..--": ",", 2192 "---...": ":", "-.-.-.": ";", 2193 "..--..": "?", "-....-": "-", 2194 "..--.-": "_", "-.--.": "(", 2195 "-.--.-": ")", ".----.": "'", 2196 "-...-": "=", ".-.-.": "+", 2197 "-..-.": "/", ".--.-.": "@", 2198 "...-..-": "$", "-.-.--": "!"} 2199char_morse = {v: k for k, v in morse_char.items()} 2200 2201 2202def encode_morse(msg, sep='|', mapping=None): 2203 """ 2204 Encodes a plaintext into popular Morse Code with letters 2205 separated by ``sep`` and words by a double ``sep``. 2206 2207 Examples 2208 ======== 2209 2210 >>> from sympy.crypto.crypto import encode_morse 2211 >>> msg = 'ATTACK RIGHT FLANK' 2212 >>> encode_morse(msg) 2213 '.-|-|-|.-|-.-.|-.-||.-.|..|--.|....|-||..-.|.-..|.-|-.|-.-' 2214 2215 References 2216 ========== 2217 2218 .. [1] https://en.wikipedia.org/wiki/Morse_code 2219 2220 """ 2221 2222 mapping = mapping or char_morse 2223 assert sep not in mapping 2224 word_sep = 2*sep 2225 mapping[" "] = word_sep 2226 suffix = msg and msg[-1] in whitespace 2227 2228 # normalize whitespace 2229 msg = (' ' if word_sep else '').join(msg.split()) 2230 # omit unmapped chars 2231 chars = set(''.join(msg.split())) 2232 ok = set(mapping.keys()) 2233 msg = translate(msg, None, ''.join(chars - ok)) 2234 2235 morsestring = [] 2236 words = msg.split() 2237 for word in words: 2238 morseword = [] 2239 for letter in word: 2240 morseletter = mapping[letter] 2241 morseword.append(morseletter) 2242 2243 word = sep.join(morseword) 2244 morsestring.append(word) 2245 2246 return word_sep.join(morsestring) + (word_sep if suffix else '') 2247 2248 2249def decode_morse(msg, sep='|', mapping=None): 2250 """ 2251 Decodes a Morse Code with letters separated by ``sep`` 2252 (default is '|') and words by `word_sep` (default is '||) 2253 into plaintext. 2254 2255 Examples 2256 ======== 2257 2258 >>> from sympy.crypto.crypto import decode_morse 2259 >>> mc = '--|---|...-|.||.|.-|...|-' 2260 >>> decode_morse(mc) 2261 'MOVE EAST' 2262 2263 References 2264 ========== 2265 2266 .. [1] https://en.wikipedia.org/wiki/Morse_code 2267 2268 """ 2269 2270 mapping = mapping or morse_char 2271 word_sep = 2*sep 2272 characterstring = [] 2273 words = msg.strip(word_sep).split(word_sep) 2274 for word in words: 2275 letters = word.split(sep) 2276 chars = [mapping[c] for c in letters] 2277 word = ''.join(chars) 2278 characterstring.append(word) 2279 rv = " ".join(characterstring) 2280 return rv 2281 2282 2283#################### LFSRs ########################################## 2284 2285 2286def lfsr_sequence(key, fill, n): 2287 r""" 2288 This function creates an LFSR sequence. 2289 2290 Parameters 2291 ========== 2292 2293 key : list 2294 A list of finite field elements, `[c_0, c_1, \ldots, c_k].` 2295 2296 fill : list 2297 The list of the initial terms of the LFSR sequence, 2298 `[x_0, x_1, \ldots, x_k].` 2299 2300 n 2301 Number of terms of the sequence that the function returns. 2302 2303 Returns 2304 ======= 2305 2306 L 2307 The LFSR sequence defined by 2308 `x_{n+1} = c_k x_n + \ldots + c_0 x_{n-k}`, for 2309 `n \leq k`. 2310 2311 Notes 2312 ===== 2313 2314 S. Golomb [G]_ gives a list of three statistical properties a 2315 sequence of numbers `a = \{a_n\}_{n=1}^\infty`, 2316 `a_n \in \{0,1\}`, should display to be considered 2317 "random". Define the autocorrelation of `a` to be 2318 2319 .. math:: 2320 2321 C(k) = C(k,a) = \lim_{N\rightarrow \infty} {1\over N}\sum_{n=1}^N (-1)^{a_n + a_{n+k}}. 2322 2323 In the case where `a` is periodic with period 2324 `P` then this reduces to 2325 2326 .. math:: 2327 2328 C(k) = {1\over P}\sum_{n=1}^P (-1)^{a_n + a_{n+k}}. 2329 2330 Assume `a` is periodic with period `P`. 2331 2332 - balance: 2333 2334 .. math:: 2335 2336 \left|\sum_{n=1}^P(-1)^{a_n}\right| \leq 1. 2337 2338 - low autocorrelation: 2339 2340 .. math:: 2341 2342 C(k) = \left\{ \begin{array}{cc} 1,& k = 0,\\ \epsilon, & k \ne 0. \end{array} \right. 2343 2344 (For sequences satisfying these first two properties, it is known 2345 that `\epsilon = -1/P` must hold.) 2346 2347 - proportional runs property: In each period, half the runs have 2348 length `1`, one-fourth have length `2`, etc. 2349 Moreover, there are as many runs of `1`'s as there are of 2350 `0`'s. 2351 2352 Examples 2353 ======== 2354 2355 >>> from sympy.crypto.crypto import lfsr_sequence 2356 >>> from sympy.polys.domains import FF 2357 >>> F = FF(2) 2358 >>> fill = [F(1), F(1), F(0), F(1)] 2359 >>> key = [F(1), F(0), F(0), F(1)] 2360 >>> lfsr_sequence(key, fill, 10) 2361 [1 mod 2, 1 mod 2, 0 mod 2, 1 mod 2, 0 mod 2, 2362 1 mod 2, 1 mod 2, 0 mod 2, 0 mod 2, 1 mod 2] 2363 2364 References 2365 ========== 2366 2367 .. [G] Solomon Golomb, Shift register sequences, Aegean Park Press, 2368 Laguna Hills, Ca, 1967 2369 2370 """ 2371 if not isinstance(key, list): 2372 raise TypeError("key must be a list") 2373 if not isinstance(fill, list): 2374 raise TypeError("fill must be a list") 2375 p = key[0].mod 2376 F = FF(p) 2377 s = fill 2378 k = len(fill) 2379 L = [] 2380 for i in range(n): 2381 s0 = s[:] 2382 L.append(s[0]) 2383 s = s[1:k] 2384 x = sum([int(key[i]*s0[i]) for i in range(k)]) 2385 s.append(F(x)) 2386 return L # use [x.to_int() for x in L] for int version 2387 2388 2389def lfsr_autocorrelation(L, P, k): 2390 """ 2391 This function computes the LFSR autocorrelation function. 2392 2393 Parameters 2394 ========== 2395 2396 L 2397 A periodic sequence of elements of `GF(2)`. 2398 L must have length larger than P. 2399 2400 P 2401 The period of L. 2402 2403 k : int 2404 An integer `k` (`0 < k < P`). 2405 2406 Returns 2407 ======= 2408 2409 autocorrelation 2410 The k-th value of the autocorrelation of the LFSR L. 2411 2412 Examples 2413 ======== 2414 2415 >>> from sympy.crypto.crypto import ( 2416 ... lfsr_sequence, lfsr_autocorrelation) 2417 >>> from sympy.polys.domains import FF 2418 >>> F = FF(2) 2419 >>> fill = [F(1), F(1), F(0), F(1)] 2420 >>> key = [F(1), F(0), F(0), F(1)] 2421 >>> s = lfsr_sequence(key, fill, 20) 2422 >>> lfsr_autocorrelation(s, 15, 7) 2423 -1/15 2424 >>> lfsr_autocorrelation(s, 15, 0) 2425 1 2426 2427 """ 2428 if not isinstance(L, list): 2429 raise TypeError("L (=%s) must be a list" % L) 2430 P = int(P) 2431 k = int(k) 2432 L0 = L[:P] # slices makes a copy 2433 L1 = L0 + L0[:k] 2434 L2 = [(-1)**(L1[i].to_int() + L1[i + k].to_int()) for i in range(P)] 2435 tot = sum(L2) 2436 return Rational(tot, P) 2437 2438 2439def lfsr_connection_polynomial(s): 2440 """ 2441 This function computes the LFSR connection polynomial. 2442 2443 Parameters 2444 ========== 2445 2446 s 2447 A sequence of elements of even length, with entries in a finite 2448 field. 2449 2450 Returns 2451 ======= 2452 2453 C(x) 2454 The connection polynomial of a minimal LFSR yielding s. 2455 2456 This implements the algorithm in section 3 of J. L. Massey's 2457 article [M]_. 2458 2459 Examples 2460 ======== 2461 2462 >>> from sympy.crypto.crypto import ( 2463 ... lfsr_sequence, lfsr_connection_polynomial) 2464 >>> from sympy.polys.domains import FF 2465 >>> F = FF(2) 2466 >>> fill = [F(1), F(1), F(0), F(1)] 2467 >>> key = [F(1), F(0), F(0), F(1)] 2468 >>> s = lfsr_sequence(key, fill, 20) 2469 >>> lfsr_connection_polynomial(s) 2470 x**4 + x + 1 2471 >>> fill = [F(1), F(0), F(0), F(1)] 2472 >>> key = [F(1), F(1), F(0), F(1)] 2473 >>> s = lfsr_sequence(key, fill, 20) 2474 >>> lfsr_connection_polynomial(s) 2475 x**3 + 1 2476 >>> fill = [F(1), F(0), F(1)] 2477 >>> key = [F(1), F(1), F(0)] 2478 >>> s = lfsr_sequence(key, fill, 20) 2479 >>> lfsr_connection_polynomial(s) 2480 x**3 + x**2 + 1 2481 >>> fill = [F(1), F(0), F(1)] 2482 >>> key = [F(1), F(0), F(1)] 2483 >>> s = lfsr_sequence(key, fill, 20) 2484 >>> lfsr_connection_polynomial(s) 2485 x**3 + x + 1 2486 2487 References 2488 ========== 2489 2490 .. [M] James L. Massey, "Shift-Register Synthesis and BCH Decoding." 2491 IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, 2492 Jan 1969. 2493 2494 """ 2495 # Initialization: 2496 p = s[0].mod 2497 x = Symbol("x") 2498 C = 1*x**0 2499 B = 1*x**0 2500 m = 1 2501 b = 1*x**0 2502 L = 0 2503 N = 0 2504 while N < len(s): 2505 if L > 0: 2506 dC = Poly(C).degree() 2507 r = min(L + 1, dC + 1) 2508 coeffsC = [C.subs(x, 0)] + [C.coeff(x**i) 2509 for i in range(1, dC + 1)] 2510 d = (s[N].to_int() + sum([coeffsC[i]*s[N - i].to_int() 2511 for i in range(1, r)])) % p 2512 if L == 0: 2513 d = s[N].to_int()*x**0 2514 if d == 0: 2515 m += 1 2516 N += 1 2517 if d > 0: 2518 if 2*L > N: 2519 C = (C - d*((b**(p - 2)) % p)*x**m*B).expand() 2520 m += 1 2521 N += 1 2522 else: 2523 T = C 2524 C = (C - d*((b**(p - 2)) % p)*x**m*B).expand() 2525 L = N + 1 - L 2526 m = 1 2527 b = d 2528 B = T 2529 N += 1 2530 dC = Poly(C).degree() 2531 coeffsC = [C.subs(x, 0)] + [C.coeff(x**i) for i in range(1, dC + 1)] 2532 return sum([coeffsC[i] % p*x**i for i in range(dC + 1) 2533 if coeffsC[i] is not None]) 2534 2535 2536#################### ElGamal ############################# 2537 2538 2539def elgamal_private_key(digit=10, seed=None): 2540 r""" 2541 Return three number tuple as private key. 2542 2543 Explanation 2544 =========== 2545 2546 Elgamal encryption is based on the mathmatical problem 2547 called the Discrete Logarithm Problem (DLP). For example, 2548 2549 `a^{b} \equiv c \pmod p` 2550 2551 In general, if ``a`` and ``b`` are known, ``ct`` is easily 2552 calculated. If ``b`` is unknown, it is hard to use 2553 ``a`` and ``ct`` to get ``b``. 2554 2555 Parameters 2556 ========== 2557 2558 digit : int 2559 Minimum number of binary digits for key. 2560 2561 Returns 2562 ======= 2563 2564 tuple : (p, r, d) 2565 p = prime number. 2566 2567 r = primitive root. 2568 2569 d = random number. 2570 2571 Notes 2572 ===== 2573 2574 For testing purposes, the ``seed`` parameter may be set to control 2575 the output of this routine. See sympy.testing.randtest._randrange. 2576 2577 Examples 2578 ======== 2579 2580 >>> from sympy.crypto.crypto import elgamal_private_key 2581 >>> from sympy.ntheory import is_primitive_root, isprime 2582 >>> a, b, _ = elgamal_private_key() 2583 >>> isprime(a) 2584 True 2585 >>> is_primitive_root(b, a) 2586 True 2587 2588 """ 2589 randrange = _randrange(seed) 2590 p = nextprime(2**digit) 2591 return p, primitive_root(p), randrange(2, p) 2592 2593 2594def elgamal_public_key(key): 2595 r""" 2596 Return three number tuple as public key. 2597 2598 Parameters 2599 ========== 2600 2601 key : (p, r, e) 2602 Tuple generated by ``elgamal_private_key``. 2603 2604 Returns 2605 ======= 2606 2607 tuple : (p, r, e) 2608 `e = r**d \bmod p` 2609 2610 `d` is a random number in private key. 2611 2612 Examples 2613 ======== 2614 2615 >>> from sympy.crypto.crypto import elgamal_public_key 2616 >>> elgamal_public_key((1031, 14, 636)) 2617 (1031, 14, 212) 2618 2619 """ 2620 p, r, e = key 2621 return p, r, pow(r, e, p) 2622 2623 2624def encipher_elgamal(i, key, seed=None): 2625 r""" 2626 Encrypt message with public key. 2627 2628 Explanation 2629 =========== 2630 2631 ``i`` is a plaintext message expressed as an integer. 2632 ``key`` is public key (p, r, e). In order to encrypt 2633 a message, a random number ``a`` in ``range(2, p)`` 2634 is generated and the encryped message is returned as 2635 `c_{1}` and `c_{2}` where: 2636 2637 `c_{1} \equiv r^{a} \pmod p` 2638 2639 `c_{2} \equiv m e^{a} \pmod p` 2640 2641 Parameters 2642 ========== 2643 2644 msg 2645 int of encoded message. 2646 2647 key 2648 Public key. 2649 2650 Returns 2651 ======= 2652 2653 tuple : (c1, c2) 2654 Encipher into two number. 2655 2656 Notes 2657 ===== 2658 2659 For testing purposes, the ``seed`` parameter may be set to control 2660 the output of this routine. See sympy.testing.randtest._randrange. 2661 2662 Examples 2663 ======== 2664 2665 >>> from sympy.crypto.crypto import encipher_elgamal, elgamal_private_key, elgamal_public_key 2666 >>> pri = elgamal_private_key(5, seed=[3]); pri 2667 (37, 2, 3) 2668 >>> pub = elgamal_public_key(pri); pub 2669 (37, 2, 8) 2670 >>> msg = 36 2671 >>> encipher_elgamal(msg, pub, seed=[3]) 2672 (8, 6) 2673 2674 """ 2675 p, r, e = key 2676 if i < 0 or i >= p: 2677 raise ValueError( 2678 'Message (%s) should be in range(%s)' % (i, p)) 2679 randrange = _randrange(seed) 2680 a = randrange(2, p) 2681 return pow(r, a, p), i*pow(e, a, p) % p 2682 2683 2684def decipher_elgamal(msg, key): 2685 r""" 2686 Decrypt message with private key. 2687 2688 `msg = (c_{1}, c_{2})` 2689 2690 `key = (p, r, d)` 2691 2692 According to extended Eucliden theorem, 2693 `u c_{1}^{d} + p n = 1` 2694 2695 `u \equiv 1/{{c_{1}}^d} \pmod p` 2696 2697 `u c_{2} \equiv \frac{1}{c_{1}^d} c_{2} \equiv \frac{1}{r^{ad}} c_{2} \pmod p` 2698 2699 `\frac{1}{r^{ad}} m e^a \equiv \frac{1}{r^{ad}} m {r^{d a}} \equiv m \pmod p` 2700 2701 Examples 2702 ======== 2703 2704 >>> from sympy.crypto.crypto import decipher_elgamal 2705 >>> from sympy.crypto.crypto import encipher_elgamal 2706 >>> from sympy.crypto.crypto import elgamal_private_key 2707 >>> from sympy.crypto.crypto import elgamal_public_key 2708 2709 >>> pri = elgamal_private_key(5, seed=[3]) 2710 >>> pub = elgamal_public_key(pri); pub 2711 (37, 2, 8) 2712 >>> msg = 17 2713 >>> decipher_elgamal(encipher_elgamal(msg, pub), pri) == msg 2714 True 2715 2716 """ 2717 p, _, d = key 2718 c1, c2 = msg 2719 u = igcdex(c1**d, p)[0] 2720 return u * c2 % p 2721 2722 2723################ Diffie-Hellman Key Exchange ######################### 2724 2725def dh_private_key(digit=10, seed=None): 2726 r""" 2727 Return three integer tuple as private key. 2728 2729 Explanation 2730 =========== 2731 2732 Diffie-Hellman key exchange is based on the mathematical problem 2733 called the Discrete Logarithm Problem (see ElGamal). 2734 2735 Diffie-Hellman key exchange is divided into the following steps: 2736 2737 * Alice and Bob agree on a base that consist of a prime ``p`` 2738 and a primitive root of ``p`` called ``g`` 2739 * Alice choses a number ``a`` and Bob choses a number ``b`` where 2740 ``a`` and ``b`` are random numbers in range `[2, p)`. These are 2741 their private keys. 2742 * Alice then publicly sends Bob `g^{a} \pmod p` while Bob sends 2743 Alice `g^{b} \pmod p` 2744 * They both raise the received value to their secretly chosen 2745 number (``a`` or ``b``) and now have both as their shared key 2746 `g^{ab} \pmod p` 2747 2748 Parameters 2749 ========== 2750 2751 digit 2752 Minimum number of binary digits required in key. 2753 2754 Returns 2755 ======= 2756 2757 tuple : (p, g, a) 2758 p = prime number. 2759 2760 g = primitive root of p. 2761 2762 a = random number from 2 through p - 1. 2763 2764 Notes 2765 ===== 2766 2767 For testing purposes, the ``seed`` parameter may be set to control 2768 the output of this routine. See sympy.testing.randtest._randrange. 2769 2770 Examples 2771 ======== 2772 2773 >>> from sympy.crypto.crypto import dh_private_key 2774 >>> from sympy.ntheory import isprime, is_primitive_root 2775 >>> p, g, _ = dh_private_key() 2776 >>> isprime(p) 2777 True 2778 >>> is_primitive_root(g, p) 2779 True 2780 >>> p, g, _ = dh_private_key(5) 2781 >>> isprime(p) 2782 True 2783 >>> is_primitive_root(g, p) 2784 True 2785 2786 """ 2787 p = nextprime(2**digit) 2788 g = primitive_root(p) 2789 randrange = _randrange(seed) 2790 a = randrange(2, p) 2791 return p, g, a 2792 2793 2794def dh_public_key(key): 2795 r""" 2796 Return three number tuple as public key. 2797 2798 This is the tuple that Alice sends to Bob. 2799 2800 Parameters 2801 ========== 2802 2803 key : (p, g, a) 2804 A tuple generated by ``dh_private_key``. 2805 2806 Returns 2807 ======= 2808 2809 tuple : int, int, int 2810 A tuple of `(p, g, g^a \mod p)` with `p`, `g` and `a` given as 2811 parameters.s 2812 2813 Examples 2814 ======== 2815 2816 >>> from sympy.crypto.crypto import dh_private_key, dh_public_key 2817 >>> p, g, a = dh_private_key(); 2818 >>> _p, _g, x = dh_public_key((p, g, a)) 2819 >>> p == _p and g == _g 2820 True 2821 >>> x == pow(g, a, p) 2822 True 2823 2824 """ 2825 p, g, a = key 2826 return p, g, pow(g, a, p) 2827 2828 2829def dh_shared_key(key, b): 2830 """ 2831 Return an integer that is the shared key. 2832 2833 This is what Bob and Alice can both calculate using the public 2834 keys they received from each other and their private keys. 2835 2836 Parameters 2837 ========== 2838 2839 key : (p, g, x) 2840 Tuple `(p, g, x)` generated by ``dh_public_key``. 2841 2842 b 2843 Random number in the range of `2` to `p - 1` 2844 (Chosen by second key exchange member (Bob)). 2845 2846 Returns 2847 ======= 2848 2849 int 2850 A shared key. 2851 2852 Examples 2853 ======== 2854 2855 >>> from sympy.crypto.crypto import ( 2856 ... dh_private_key, dh_public_key, dh_shared_key) 2857 >>> prk = dh_private_key(); 2858 >>> p, g, x = dh_public_key(prk); 2859 >>> sk = dh_shared_key((p, g, x), 1000) 2860 >>> sk == pow(x, 1000, p) 2861 True 2862 2863 """ 2864 p, _, x = key 2865 if 1 >= b or b >= p: 2866 raise ValueError(filldedent(''' 2867 Value of b should be greater 1 and less 2868 than prime %s.''' % p)) 2869 2870 return pow(x, b, p) 2871 2872 2873################ Goldwasser-Micali Encryption ######################### 2874 2875 2876def _legendre(a, p): 2877 """ 2878 Returns the legendre symbol of a and p 2879 assuming that p is a prime. 2880 2881 i.e. 1 if a is a quadratic residue mod p 2882 -1 if a is not a quadratic residue mod p 2883 0 if a is divisible by p 2884 2885 Parameters 2886 ========== 2887 2888 a : int 2889 The number to test. 2890 2891 p : prime 2892 The prime to test ``a`` against. 2893 2894 Returns 2895 ======= 2896 2897 int 2898 Legendre symbol (a / p). 2899 2900 """ 2901 sig = pow(a, (p - 1)//2, p) 2902 if sig == 1: 2903 return 1 2904 elif sig == 0: 2905 return 0 2906 else: 2907 return -1 2908 2909 2910def _random_coprime_stream(n, seed=None): 2911 randrange = _randrange(seed) 2912 while True: 2913 y = randrange(n) 2914 if gcd(y, n) == 1: 2915 yield y 2916 2917 2918def gm_private_key(p, q, a=None): 2919 """ 2920 Check if ``p`` and ``q`` can be used as private keys for 2921 the Goldwasser-Micali encryption. The method works 2922 roughly as follows. 2923 2924 Explanation 2925 =========== 2926 2927 $\\cdot$ Pick two large primes $p$ and $q$. 2928 2929 $\\cdot$ Call their product $N$. 2930 2931 $\\cdot$ Given a message as an integer $i$, write $i$ in its 2932 bit representation $b_0$ , $\\dotsc$ , $b_n$ . 2933 2934 $\\cdot$ For each $k$ , 2935 2936 if $b_k$ = 0: 2937 let $a_k$ be a random square 2938 (quadratic residue) modulo $p q$ 2939 such that $jacobi \\_symbol(a, p q) = 1$ 2940 if $b_k$ = 1: 2941 let $a_k$ be a random non-square 2942 (non-quadratic residue) modulo $p q$ 2943 such that $jacobi \\_ symbol(a, p q) = 1$ 2944 2945 returns [$a_1$ , $a_2$ , $\\dotsc$ ] 2946 2947 $b_k$ can be recovered by checking whether or not 2948 $a_k$ is a residue. And from the $b_k$ 's, the message 2949 can be reconstructed. 2950 2951 The idea is that, while $jacobi \\_ symbol(a, p q)$ 2952 can be easily computed (and when it is equal to $-1$ will 2953 tell you that $a$ is not a square mod $p q$ ), quadratic 2954 residuosity modulo a composite number is hard to compute 2955 without knowing its factorization. 2956 2957 Moreover, approximately half the numbers coprime to $p q$ have 2958 $jacobi \\_ symbol$ equal to $1$ . And among those, approximately half 2959 are residues and approximately half are not. This maximizes the 2960 entropy of the code. 2961 2962 Parameters 2963 ========== 2964 2965 p, q, a 2966 Initialization variables. 2967 2968 Returns 2969 ======= 2970 2971 tuple : (p, q) 2972 The input value ``p`` and ``q``. 2973 2974 Raises 2975 ====== 2976 2977 ValueError 2978 If ``p`` and ``q`` are not distinct odd primes. 2979 2980 """ 2981 if p == q: 2982 raise ValueError("expected distinct primes, " 2983 "got two copies of %i" % p) 2984 elif not isprime(p) or not isprime(q): 2985 raise ValueError("first two arguments must be prime, " 2986 "got %i of %i" % (p, q)) 2987 elif p == 2 or q == 2: 2988 raise ValueError("first two arguments must not be even, " 2989 "got %i of %i" % (p, q)) 2990 return p, q 2991 2992 2993def gm_public_key(p, q, a=None, seed=None): 2994 """ 2995 Compute public keys for ``p`` and ``q``. 2996 Note that in Goldwasser-Micali Encryption, 2997 public keys are randomly selected. 2998 2999 Parameters 3000 ========== 3001 3002 p, q, a : int, int, int 3003 Initialization variables. 3004 3005 Returns 3006 ======= 3007 3008 tuple : (a, N) 3009 ``a`` is the input ``a`` if it is not ``None`` otherwise 3010 some random integer coprime to ``p`` and ``q``. 3011 3012 ``N`` is the product of ``p`` and ``q``. 3013 3014 """ 3015 3016 p, q = gm_private_key(p, q) 3017 N = p * q 3018 3019 if a is None: 3020 randrange = _randrange(seed) 3021 while True: 3022 a = randrange(N) 3023 if _legendre(a, p) == _legendre(a, q) == -1: 3024 break 3025 else: 3026 if _legendre(a, p) != -1 or _legendre(a, q) != -1: 3027 return False 3028 return (a, N) 3029 3030 3031def encipher_gm(i, key, seed=None): 3032 """ 3033 Encrypt integer 'i' using public_key 'key' 3034 Note that gm uses random encryption. 3035 3036 Parameters 3037 ========== 3038 3039 i : int 3040 The message to encrypt. 3041 3042 key : (a, N) 3043 The public key. 3044 3045 Returns 3046 ======= 3047 3048 list : list of int 3049 The randomized encrypted message. 3050 3051 """ 3052 if i < 0: 3053 raise ValueError( 3054 "message must be a non-negative " 3055 "integer: got %d instead" % i) 3056 a, N = key 3057 bits = [] 3058 while i > 0: 3059 bits.append(i % 2) 3060 i //= 2 3061 3062 gen = _random_coprime_stream(N, seed) 3063 rev = reversed(bits) 3064 encode = lambda b: next(gen)**2*pow(a, b) % N 3065 return [ encode(b) for b in rev ] 3066 3067 3068 3069def decipher_gm(message, key): 3070 """ 3071 Decrypt message 'message' using public_key 'key'. 3072 3073 Parameters 3074 ========== 3075 3076 message : list of int 3077 The randomized encrypted message. 3078 3079 key : (p, q) 3080 The private key. 3081 3082 Returns 3083 ======= 3084 3085 int 3086 The encrypted message. 3087 3088 """ 3089 p, q = key 3090 res = lambda m, p: _legendre(m, p) > 0 3091 bits = [res(m, p) * res(m, q) for m in message] 3092 m = 0 3093 for b in bits: 3094 m <<= 1 3095 m += not b 3096 return m 3097 3098 3099 3100########### RailFence Cipher ############# 3101 3102def encipher_railfence(message,rails): 3103 """ 3104 Performs Railfence Encryption on plaintext and returns ciphertext 3105 3106 Examples 3107 ======== 3108 3109 >>> from sympy.crypto.crypto import encipher_railfence 3110 >>> message = "hello world" 3111 >>> encipher_railfence(message,3) 3112 'horel ollwd' 3113 3114 Parameters 3115 ========== 3116 3117 message : string, the message to encrypt. 3118 rails : int, the number of rails. 3119 3120 Returns 3121 ======= 3122 3123 The Encrypted string message. 3124 3125 References 3126 ========== 3127 .. [1] https://en.wikipedia.org/wiki/Rail_fence_cipher 3128 3129 """ 3130 r = list(range(rails)) 3131 p = cycle(r + r[-2:0:-1]) 3132 return ''.join(sorted(message, key=lambda i: next(p))) 3133 3134 3135def decipher_railfence(ciphertext,rails): 3136 """ 3137 Decrypt the message using the given rails 3138 3139 Examples 3140 ======== 3141 3142 >>> from sympy.crypto.crypto import decipher_railfence 3143 >>> decipher_railfence("horel ollwd",3) 3144 'hello world' 3145 3146 Parameters 3147 ========== 3148 3149 message : string, the message to encrypt. 3150 rails : int, the number of rails. 3151 3152 Returns 3153 ======= 3154 3155 The Decrypted string message. 3156 3157 """ 3158 r = list(range(rails)) 3159 p = cycle(r + r[-2:0:-1]) 3160 3161 idx = sorted(range(len(ciphertext)), key=lambda i: next(p)) 3162 res = [''] * len(ciphertext) 3163 for i, c in zip(idx, ciphertext): 3164 res[i] = c 3165 return ''.join(res) 3166 3167 3168################ Blum-Goldwasser cryptosystem ######################### 3169 3170def bg_private_key(p, q): 3171 """ 3172 Check if p and q can be used as private keys for 3173 the Blum-Goldwasser cryptosystem. 3174 3175 Explanation 3176 =========== 3177 3178 The three necessary checks for p and q to pass 3179 so that they can be used as private keys: 3180 3181 1. p and q must both be prime 3182 2. p and q must be distinct 3183 3. p and q must be congruent to 3 mod 4 3184 3185 Parameters 3186 ========== 3187 3188 p, q 3189 The keys to be checked. 3190 3191 Returns 3192 ======= 3193 3194 p, q 3195 Input values. 3196 3197 Raises 3198 ====== 3199 3200 ValueError 3201 If p and q do not pass the above conditions. 3202 3203 """ 3204 3205 if not isprime(p) or not isprime(q): 3206 raise ValueError("the two arguments must be prime, " 3207 "got %i and %i" %(p, q)) 3208 elif p == q: 3209 raise ValueError("the two arguments must be distinct, " 3210 "got two copies of %i. " %p) 3211 elif (p - 3) % 4 != 0 or (q - 3) % 4 != 0: 3212 raise ValueError("the two arguments must be congruent to 3 mod 4, " 3213 "got %i and %i" %(p, q)) 3214 return p, q 3215 3216def bg_public_key(p, q): 3217 """ 3218 Calculates public keys from private keys. 3219 3220 Explanation 3221 =========== 3222 3223 The function first checks the validity of 3224 private keys passed as arguments and 3225 then returns their product. 3226 3227 Parameters 3228 ========== 3229 3230 p, q 3231 The private keys. 3232 3233 Returns 3234 ======= 3235 3236 N 3237 The public key. 3238 3239 """ 3240 p, q = bg_private_key(p, q) 3241 N = p * q 3242 return N 3243 3244def encipher_bg(i, key, seed=None): 3245 """ 3246 Encrypts the message using public key and seed. 3247 3248 Explanation 3249 =========== 3250 3251 ALGORITHM: 3252 1. Encodes i as a string of L bits, m. 3253 2. Select a random element r, where 1 < r < key, and computes 3254 x = r^2 mod key. 3255 3. Use BBS pseudo-random number generator to generate L random bits, b, 3256 using the initial seed as x. 3257 4. Encrypted message, c_i = m_i XOR b_i, 1 <= i <= L. 3258 5. x_L = x^(2^L) mod key. 3259 6. Return (c, x_L) 3260 3261 Parameters 3262 ========== 3263 3264 i 3265 Message, a non-negative integer 3266 3267 key 3268 The public key 3269 3270 Returns 3271 ======= 3272 3273 Tuple 3274 (encrypted_message, x_L) 3275 3276 Raises 3277 ====== 3278 3279 ValueError 3280 If i is negative. 3281 3282 """ 3283 3284 if i < 0: 3285 raise ValueError( 3286 "message must be a non-negative " 3287 "integer: got %d instead" % i) 3288 3289 enc_msg = [] 3290 while i > 0: 3291 enc_msg.append(i % 2) 3292 i //= 2 3293 enc_msg.reverse() 3294 L = len(enc_msg) 3295 3296 r = _randint(seed)(2, key - 1) 3297 x = r**2 % key 3298 x_L = pow(int(x), int(2**L), int(key)) 3299 3300 rand_bits = [] 3301 for _ in range(L): 3302 rand_bits.append(x % 2) 3303 x = x**2 % key 3304 3305 encrypt_msg = [m ^ b for (m, b) in zip(enc_msg, rand_bits)] 3306 3307 return (encrypt_msg, x_L) 3308 3309def decipher_bg(message, key): 3310 """ 3311 Decrypts the message using private keys. 3312 3313 Explanation 3314 =========== 3315 3316 ALGORITHM: 3317 1. Let, c be the encrypted message, y the second number received, 3318 and p and q be the private keys. 3319 2. Compute, r_p = y^((p+1)/4 ^ L) mod p and 3320 r_q = y^((q+1)/4 ^ L) mod q. 3321 3. Compute x_0 = (q(q^-1 mod p)r_p + p(p^-1 mod q)r_q) mod N. 3322 4. From, recompute the bits using the BBS generator, as in the 3323 encryption algorithm. 3324 5. Compute original message by XORing c and b. 3325 3326 Parameters 3327 ========== 3328 3329 message 3330 Tuple of encrypted message and a non-negative integer. 3331 3332 key 3333 Tuple of private keys. 3334 3335 Returns 3336 ======= 3337 3338 orig_msg 3339 The original message 3340 3341 """ 3342 3343 p, q = key 3344 encrypt_msg, y = message 3345 public_key = p * q 3346 L = len(encrypt_msg) 3347 p_t = ((p + 1)/4)**L 3348 q_t = ((q + 1)/4)**L 3349 r_p = pow(int(y), int(p_t), int(p)) 3350 r_q = pow(int(y), int(q_t), int(q)) 3351 3352 x = (q * mod_inverse(q, p) * r_p + p * mod_inverse(p, q) * r_q) % public_key 3353 3354 orig_bits = [] 3355 for _ in range(L): 3356 orig_bits.append(x % 2) 3357 x = x**2 % public_key 3358 3359 orig_msg = 0 3360 for (m, b) in zip(encrypt_msg, orig_bits): 3361 orig_msg = orig_msg * 2 3362 orig_msg += (m ^ b) 3363 3364 return orig_msg 3365