<jupyter_start><jupyter_text>SecretsChapter 4 of [Real World Algorithms](https://mitpress.mit.edu/books/real-world-algorithms).---> <NAME>> Athens University of Economics and Business  Substitution CipherThe simplest encryption and decryption scheme is probably a substitution cipher, also known as Caesar cipher.In Python, we takeeach character's encoding, via `ord()`. We calculate its position in the alphabet by subtracting the encoding for `A`.We add a `shift` to it, taking care to wrap around if we get past 26 (the number of letters in our alphabet).The result is the position in the alphabet of the encrypted character, so we add it to the position of `A` to get its actual encoding. We convert the encoding to a character with `chr()`.In our example we assume that we encrypt texts containing only upper case latin characters.<jupyter_code>import io

def caesar_cipher(plaintext, shift):
    ciphertext = [ chr((ord(c) - ord('A') + shift) % 26 + ord('A')) 
                  for c in plaintext ]
    return ''.join(ciphertext)
    
ciphertext = caesar_cipher('IAMSEATEDINANOFFICE', 5)
print(ciphertext)<jupyter_output>NFRXJFYJINSFSTKKNHJ<jupyter_text>Decryption is really the same think as encryption, we just use the opposite shift:<jupyter_code>print(caesar_cipher(ciphertext, -5))<jupyter_output>IAMSEATEDINANOFFICE<jupyter_text>Needless to say, this is not a good cipher. As we have not taken out the spaces between the words, one can even make out the structure of the text.To break the decryption, one only needs to try different shifts.  One-time PadThe only truly unbreakable cipher is the one-time pad.To implement a simple version of it, we will use a helper function that returns the position of a character in the alphabet.Again, we assume that we work with messages composed only of upper case latin characters.<jupyter_code>def ord0(c):
    return ord(c) - ord('A')<jupyter_output><empty_output><jupyter_text>This is then the one-time pad encryption function:<jupyter_code>def otpad_encrypt(plaintext, randomtext):
    encrypted = [ chr((ord0(c) + ord0(r)) % 26 + ord('A')) 
                 for c, r in zip(plaintext, randomtext) ]
    return ''.join(encrypted)<jupyter_output><empty_output><jupyter_text>To see it in action:<jupyter_code>plaintext = "IFYOUREALLYWANTTO"
randomtext = "RDUUWJEMCJJXZDOWJ"

ciphertext = otpad_encrypt(plaintext, randomtext)
print(ciphertext)<jupyter_output>ZISIQAIMNUHTZQHPX<jupyter_text>Decryption is similar, but we subtract instead of adding:<jupyter_code>def otpad_decrypt(ciphertext, randomtext):
    decrypted = [ chr((ord0(c) - ord0(r)) % 26 + ord('A')) 
                 for c, r in zip(ciphertext, randomtext) ]
    return ''.join(decrypted)<jupyter_output><empty_output><jupyter_text>So we can now decrypt the message we encrypted:<jupyter_code>plaintext = otpad_decrypt(ciphertext, randomtext)
print(plaintext)<jupyter_output>IFYOUREALLYWANTTO<jupyter_text>A one-time pad is impossible to decrypt unless you know the random text that has been used as the encryption key.In fact, you can always invent a random text that decrypts to something sensible, but completely irrelevant to the original plaintext.Let us write a function that does that, for the purpose of confusing our opponents.<jupyter_code>def otpad_red_herring(plaintext, ciphertext):
    red_herring = [ chr((ord0(c) - ord0(p)) % 26 + ord('A'))
                   for p, c in zip(plaintext, ciphertext) ]
    return ''.join(red_herring)

red_herring = otpad_red_herring("IAMSEATEDINANOFFI", ciphertext)
print(red_herring)<jupyter_output>RIGQMAPIKMUTMCCKP<jupyter_text>So now we can leak `<KEY>` as the key, and the opponent will then decrypt:<jupyter_code>print(otpad_decrypt(ciphertext, red_herring))<jupyter_output>IAMSEATEDINANOFFI<jupyter_text>Or anything else we like, for instance:<jupyter_code>red_herring = otpad_red_herring("RENDEZVOUSATNIGHT", ciphertext)
print(red_herring)<jupyter_output>IEFFMBNYTCHAMIBIE<jupyter_text>That will happily decrypt our initial ciphertext again:<jupyter_code>print(otpad_decrypt(ciphertext, red_herring))<jupyter_output>RENDEZVOUSATNIGHT<jupyter_text>When working with a one-time pad, we don't really need to do addition and subtraction on the positions of the letters in the alphabet.It is more convenient and faster to use the XOR operation.For encryption, we just XOR the plaintext and the randomtext:<jupyter_code>def otpad_xencrypt(plaintext, randomtext):
    encrypted = [ chr(ord(p) ^ ord(r)) for p, r in zip(plaintext, randomtext) ]
    return ''.join(encrypted)<jupyter_output><empty_output><jupyter_text>So we can now see how it works:<jupyter_code>ciphertext = otpad_xencrypt(plaintext, randomtext)
print(ciphertext)<jupyter_output>
<jupyter_text>In fact we see nothing!That is because the encrypted string is composed entirely of non-printable ASCII characters or whitespace.If we really want to, we can print its hexadecimal representation.<jupyter_code>print(ciphertext.encode('utf8'))<jupyter_output>b'\x1b\x02\x0c\x1a\x02\x18\x00\x0c\x0f\x06\x13\x0f\x1b\n\x1b\x03\x05'<jupyter_text>Decryption now is exactly the same with encryption, but we use the ciphertext and the random text:<jupyter_code>decrypted = otpad_xencrypt(ciphertext, randomtext)

print(decrypted)<jupyter_output>IFYOUREALLYWANTTO<jupyter_text>AESNo, we are not going to give an implementation of AES here.The algorithm is very complicated, and a real implementation would go well beyond the scope of this notebook.  Diffie-Hellman Key ExchangeThe Diffie-Hellman key exchange scheme is based on the discrete logarithm problem.That is, it is very difficult to find $x$ from the value of $g^x \bmod p$, if $g$ and $p$ are chosen carefully. For example, see what is happening for $g = 2$ and $p = 13$.$g^x$ is predictable, but $g^x \bmod p$ does not show any pattern.Note that, in what follows, we are going to use Python's function `pow()`. Although Python has an operator for exponentiation (`**`), `pow()` is useful because it can either be called as `pow(x, y)` to return $x^y$, or `pow(x, y, p)` to return $x^y \bmod p$.<jupyter_code>g = 2
p = 13

for x in range(1, 13):
    print(pow(g, x), pow(g, x, p))<jupyter_output>2 2
4 4
8 8
16 3
32 6
64 12
128 11
256 9
512 5
1024 10
2048 7
4096 1<jupyter_text>To see how Diffie-Hellman works, let us take Alice and Bob.Alice and Bob agree on $g$ and $p$.They choose $p = 2^{4096} - 2^{4032} - 1 + 2^{64} \times [ (2^{3966} \pi) + 240904 ]$.Yes, this is a terrifying number. It is 4096 bits long.No, Alice and Bob did not got it out of thin air. They chose it from a [list of published recommendations](https://tools.ietf.org/html/rfc3526section-5).The hexadecimal value of $p$ is equal to:```FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD129024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DDEF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7EDEE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3DC2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3BE39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA051015728E5A 8AAAC42D AD33170D 04507A33 A85521AB DF1CBA64ECFB8504 58DBEF0A 8AEA7157 5D060C7D B3970F85 A6E1E4C7ABF5AE8C DB0933D7 1E8C94E0 4A25619D CEE3D226 1AD2EE6BF12FFA06 D98A0864 D8760273 3EC86A64 521F2B18 177B200CBBE11757 7A615D6C 770988C0 BAD946E2 08E24FA0 74E5AB3143DB5BFC E0FD108E 4B82D120 A9210801 1A723C12 A787E6D788719A10 BDBA5B26 99C32718 6AF4E23C 1A946834 B6150BDA2583E9CA 2AD44CE8 DBBBC2DB 04DE8EF9 2E8EFC14 1FBECAA6287C5947 4E6BC05D 99B2964F A090C3A2 233BA186 515BE7ED1F612970 CEE2D7AF B81BDD76 2170481C D0069127 D5B05AA993B4EA98 8D8FDDC1 86FFB7DC 90A6C08F 4DF435C9 34063199FFFFFFFF FFFFFFFF```<jupyter_code>p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64\
ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7\
ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B\
F12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31\
43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7\
88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA\
2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6\
287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED\
1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9\
93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199\
FFFFFFFFFFFFFFFF<jupyter_output><empty_output><jupyter_text>Then, again following the recommendations, they choose $g = 2$.<jupyter_code>g = 2<jupyter_output><empty_output><jupyter_text>After settling for $p$ and $g$ with Bob, she picks a secret number $a$.We want $a$ to be big, 256 bits long.Alice can pick $a$ in random.<jupyter_code>import random

a = random.getrandbits(256)
print(a)<jupyter_output>10785370814603608441518857787858058637153974855022796500916983771692574257075<jupyter_text>She calculates $A = g^a \bmod p$.She sends $A$ to Bob.<jupyter_code>alice_to_bob = pow(g, a, p)
print(alice_to_bob)<jupyter_output>6714259846189483024486111424410085514165322919334348028872179658063961707492820917646144439051549610567866128455689997022980898165225598676439014861497901831417772716753946672197909062797762756440153409673875887936663132169564140465081302758813842887232490384478519021460214923937722547551917546054609676413564772741674711627909601721906498323790428215129698463507197001760428510424784309912897687043559553920672693344550476609091155261024678624502681474323741125370906777803047583208086974407479658151013578596693079647797933578546150572511096149575653228990677939503650201866421611545931642662739632890919736541640863648560536857557367974792574791774856816008508617791674344038453243221915992753984795741505944006029036205623321561675187613223626075414633955680072401669949983249798293279381586655469578014577119278489110135421557417810196701272578524120813212607362295615322509224551670243492256048437424629132829638934231332392025118908570580277138030422883233631636870678115990998956124570393810[...]<jupyter_text>Bob uses the same values for $p$ and $g$.He picks a secret number $b$.He calculates $B = g^b \bmod p$.He sends $B$ to Alice.<jupyter_code>p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1\
29024E088A67CC74020BBEA63B139B22514A08798E3404DD\
EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245\
E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED\
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D\
C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F\
83655D23DCA3AD961C62F356208552BB9ED529077096966D\
670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B\
E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9\
DE2BCBF6955817183995497CEA956AE515D2261898FA0510\
15728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64\
ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7\
ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6B\
F12FFA06D98A0864D87602733EC86A64521F2B18177B200C\
BBE117577A615D6C770988C0BAD946E208E24FA074E5AB31\
43DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D7\
88719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA\
2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6\
287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED\
1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA9\
93B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199\
FFFFFFFFFFFFFFFF 

g = 2

b = random.getrandbits(256)
print('b =', b)

bob_to_alice = pow(g, b, p)
print(bob_to_alice)<jupyter_output>b = 85683632716075647490468894737054020435795289996303502038870365640053543961208
342679346139328404094596667028843589010078116349706026625336869729589261898982386212425318536065212538984412314931253380181511065051931846665290927340474823927059095619189735482288701017197437808964409337207224538540230055701012417549321775430552677549122701047948609062484733541584331831271665750946668362564099771684237862823255156992140337828642757722886727567489837212325958608671423412930950742574585110513877045425948511566732644635196931765116696613589653403013148159853726825373317822764288866251127990135361424205576478280796587385206388113044638664298584443458812113956039868961425464512008904553677677409072610672186323390195708683546326121952969386432024406716672043105218900478431077297639369563630449321808160756315077496453340767811070829411843375756392563019621973643623609913406555324098584884376838192083810961644766385375514861417314852259617932981332889170180606236001600602915879489470231450194109[...]<jupyter_text>Then Alice calculates $B^a \bmod b$:<jupyter_code>shared_secret_alice = pow(bob_to_alice, a, p)
print(shared_secret_alice)<jupyter_output>2455540082582703901369979034711670571373998921896592884084488118499498495223052354034128092700936008229490322102177225779990958720304958480646772876581842065934393646763798114033902852601741675550686613580062859411579560645204232688284798556290611130633016820418890081318168511106024696830147659836535239473553981828824358705671107529453513700781334719997050039504410291479560158413645261093342737695916456376626705540094368474772755505273752879613237679836060125618659030435871932514801599406498672499357482909074210943580402631373486469222869335643118280168588467005963798587652744697868910643999392203434957350568868356869962355314965430286546896895295037467242878142198316023771305964326626403464823909996045427349255920175282137051368691522725113088885562544850763889424367257618833772330029264344249377789343926961753181204999112830049590171099775374382300829017944939585323806948877129433375336741402530217461521366669646565067602231658556402275920328096022008436440076005677459998098412658274[...]<jupyter_text>And Bob calculates $A^b \bmod p$:<jupyter_code>shared_secret_bob = pow(alice_to_bob, b, p)
print(shared_secret_bob)<jupyter_output>2455540082582703901369979034711670571373998921896592884084488118499498495223052354034128092700936008229490322102177225779990958720304958480646772876581842065934393646763798114033902852601741675550686613580062859411579560645204232688284798556290611130633016820418890081318168511106024696830147659836535239473553981828824358705671107529453513700781334719997050039504410291479560158413645261093342737695916456376626705540094368474772755505273752879613237679836060125618659030435871932514801599406498672499357482909074210943580402631373486469222869335643118280168588467005963798587652744697868910643999392203434957350568868356869962355314965430286546896895295037467242878142198316023771305964326626403464823909996045427349255920175282137051368691522725113088885562544850763889424367257618833772330029264344249377789343926961753181204999112830049590171099775374382300829017944939585323806948877129433375336741402530217461521366669646565067602231658556402275920328096022008436440076005677459998098412658274[...]<jupyter_text>They arrived at the same result.That is their secret secret.<jupyter_code>shared_secret_alice == shared_secret_bob<jupyter_output><empty_output><jupyter_text>Modular ExponentiationWe saw that we are dealing with huge numbers.We need efficient implementations of the arithmetic operations.In particular, we want fast exponentiation and fast modular exponentiation.Python already implements fast operations---otherwise we would not be able to run this workbook.But it is worth seeing how such algorithms look like. Exponentiation by repeated squaring is a direct application of the algorithm in the book.Instead of calculating $d \bmod 2$, we calculate simply `d & 0b1`.That performs a bitwise AND operation between `d` and the single bit `1`. It therefore checks whether the last digit of `d` is one, which is equivalent to whether it is an odd number.Then, to perform integer division by 2, that is, $\lfloor d / 2\rfloor$, we only need to shift right d by one bit, `d >> 1`.We also add a statement to print the progress of the calculation, so that we get the values of $c$, $r$, and $d$ of Table 4.9 in the book.<jupyter_code>def exponentiation(g, x):
    print('{0:>10} {1:>10} {2:>10}'.format('c', 'r', 'd'))
    c = g
    d = x
    r = 1
    while d > 0:
        print(f'{c:-10d} {r:-10d} {bin(d):>10}')
        if d & 0b1 == 1:
            r = r * c
        d = d >> 1
        c = c * c
    return r

exponentiation(13, 13)<jupyter_output>c          r          d
        13          1     0b1101
       169         13      0b110
     28561         13       0b11
 815730721     371293        0b1<jupyter_text>The modular exponentiation by repeated squaring is almost the same function.The only change is that the calculations of `r` and `c` inside the loop are done modulo `p`.<jupyter_code>def mod_exponentiation(g, x, p):
    print('{0:>10} {1:>10} {2:>10}'.format('c', 'r', 'd'))
    c = g % p
    d = x
    r = 1
    while d > 0:
        print(f'{c:-10d} {r:-10d} {bin(d):>10}')
        if d & 0b1 == 1:
            r = (r * c) % p
        d = d >> 1
        c = (c * c) % p
    return r

mod_exponentiation(155, 235, 391)<jupyter_output>c          r          d
       155          1 0b11101011
       174        155  0b1110101
       169        382   0b111010
        18        382    0b11101
       324        229     0b1110
       188        229      0b111
       154         42       0b11
       256        212        0b1
{'fraction_non_alphanumeric': 0.060714285714285714, 'fraction_numerical': 0.3562358276643991, 'mean_word_length': 7.212756052141527, 'pattern_counts': {'":': 0, '<': 88, '<?xml version=': 0, '>': 106, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 8, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '26', 'dir': 'jupyter-structured-clean-dedup', 'id': '183966', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 10705, 'n_tokens_neox': 7054, 'n_words': 1323, 'path': 'chapter_04_Secrets.ipynb', 'repo_name': 'ioef/Real_World_Algorithms', 'size': '17660'}