def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)
    
print(euclid(160, 144))

"""
Explanation: Split Secrets

Chapter 5 of Real World Algorithms.



Panos Louridas<br />
Athens University of Economics and Business

The RSA Cryptosystem
The security of the RSA cryptosystem is based on the difficulty of factoring.
That is, given a number, it is difficult to find its prime factors.
But to arrive at the RSA cryptosystem itself, we need first to see first some algorithms from Number Theory.
Euclid's algorithm allows us to find the Greatest Common Divisor (gcd) of two numbers.
End of explanation
"""


print(euclid(144, 160))

"""
Explanation: The algorithm is recursive.
To find the gcd of $a$ and $b$ is equivalent to finding the GCD of $a$ and $a \bmod b$, unless $b$ is zero, in which case the gcd is $a$.
It does not matter which of $a$, $b$ is bigger, the algorithm will provide the same answer.
End of explanation
"""


def trace_euclid(a, b):
    print('GCD of', a, b)
    if b == 0:
        return a
    else:
        return trace_euclid(b, a % b)

print(trace_euclid(160, 144))
print(trace_euclid(144, 160))

"""
Explanation: To see why this happens, and to get a better understanding at the workings of the algorithm, we can include some tracing information in the code.
End of explanation
"""


144 % 160 == 144

"""
Explanation: So, what happens is that when $a < b$, $a$ and $b$ are swapped in the first recursive call.
That is because if $a < b$, then $a \bmod b = a$.
End of explanation
"""


def extended_euclid(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        (d, x, y) = extended_euclid(b, a % b)
        return (d, y, x - (a // b) * y)
    
print(extended_euclid(3, 352))

"""
Explanation: The next step is the Extended Euclid's Algorithm.
This algorithm gives us the GCD of $a$ and $b$ and two numbers $x$ and $y$ such that:
$$ GCD(a, b) = xa + yb$$
End of explanation
"""


(d, x, y) = extended_euclid(3, 352)
d == x * 3 + y * 352

"""
Explanation: Indeed, we can verify that the GCD of 3 and 352 is 1 and that:
$$ 1 = -117 \times 3 + 352 \times 1$$
End of explanation
"""


def trace_extended_euclid(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        print('Going down', a, b, a % b)
        (d, x, y) = trace_extended_euclid(b, a % b)
        print('Going up', d, x, y)
        return (d, y, x - (a // b) * y)
    
print(trace_extended_euclid(3, 352))

"""
Explanation: Again, we can gain a better understanding by tracing the algorithm.
In the following, Going down means that we make recursive calls (so we go add to the recursion stack) and Going up means that we have returned from recursive calls (so we make our way up, unwinding the recursion stack).
In effect, they are the left and the right part of Figure 5.2 in the book.
End of explanation
"""


def modular_inverse(a, n):
    (r, x, y) = extended_euclid(a, n) 
    if r != 1:
        return 0 
    elif x < 0:
        return x + n
    else:
        return x

"""
Explanation: We need the Extended Euclid's Algorithm in order to find the modular inverse of a number $a$ modulo $n$.
The inverse of a number $a$, is the number that we denote by $a^{-1}$ such that $a a^{-1} = 1$.
If we move over to arithmetic modulo $n$, we obtain a similar definition for the modular inverse.
The modular inverse of a number $a$ modulo $n$, is the number we denote by $a^{-1} \bmod n$ such that $a a^{-1} \bmod n = 1$.
To find the modular inverse of a number $a$ modulo $n$, we run the Extended Euclid's Algorithm with input $a$ and $n$.
The algorithm will return a triplet $(r, x, y)$. 
If $r = 1$ it means we have:
$$ 1 = ax + nb$$
Therefore:
$$ ax = 1 - bn$$
But that is equivalent to:
$$ ax \bmod n = 1$$
So, $x$ is the modular inverse of $a$ modulo $n$.
If $r \ne 1$, then the modular inverse does not exist.
Note that the Extended Euclid's Algorithm may return $(r, x, y)$ with $x < 0$.
If this happens, the modular inverse is $x + n$.
With all this, the function for finding the modular inverse is:
End of explanation
"""


modular_inverse(6, 31)

"""
Explanation: For example, let's take $n = 31$ and $a = 6$.
End of explanation
"""


(6 * 26) % 31 == 1

"""
Explanation: We can verify that it is correct:
End of explanation
"""


p_alice = 17
q_alice = 23
n_alice = p_alice * q_alice
print(n_alice)

"""
Explanation: Now we can see the RSA cryptosystem in action.
Alice picks two primes, say $p = 17$ and $q = 23$.
She calculates $n = pq$.
End of explanation
"""


e_alice = 3
phi_alice = (p_alice - 1)*(q_alice - 1)
d_alice = modular_inverse(e_alice, phi_alice)
print(d_alice)

"""
Explanation: Alice then chooses a number $e$ that is relatively prime to $(p - 1)(q - 1)$.
Say she picks $e = 3$.
She then finds the modular inverse of $e$ modulo $(p - 1)(q - 1)$.
End of explanation
"""


m = 314
c = pow(m, e_alice, n_alice)
print(c)

"""
Explanation: Alice's public key is $(e, n) = (3, 391)$.
Her private key is $(d, n) = (235, 391)$.
If Bob wants to encrypt, say, the message $M = 314$ and send it to Alice, he takes her public key and performs the following operation:
$$ M^e \bmod n$$
End of explanation
"""


dec_c = pow(c, d_alice, n_alice)
print(dec_c)

"""
Explanation: The encrypted message is $C = 155$, which he sends to Alice.
To decrypt the message, Alice uses her private key and performs the following operation:
$$C^d \bmod n$$
End of explanation
"""


sig_c = pow(m, d_alice, n_alice)
print(sig_c)

"""
Explanation: So she did decrypt $C$ to the correct message.
Signing a message works in the same way, only the roles of the public and the private key are interchanged.
If Alice wants to sign, say, the message $M = 314$ and send it to Bob, she takes her public key and performs the following operation:
$$M^d \bmod n$$
End of explanation
"""


pow(sig_c, e_alice, n_alice) == m

"""
Explanation: The signature is $S = 274$, which she sends to Bob, along with $M = 314$.
Bob can then verify that the sender is indeed Alice by taking her public key and performing the following operation:
$$S^e \bmod n$$
End of explanation
"""


p_bob = 31
q_bob = 43
n_bob = 31 * 43
print(n_bob)
phi_bob = (p_bob - 1) * (q_bob - 1)
print(phi_bob)

"""
Explanation: As we saw, this allows Bob to verify that Alice was the sender, but Alice sends her message as plaintext to Bob.
If she wants to encrypt it, then she will encrypt the message and the signature with Bob's public key.
Bob will decrypt the message and the signagure and then will check the signature against the decrypted message.
Suppose that Bob has selected $p = 31$, $q = 43$.
End of explanation
"""


e_bob = 23
d_bob = modular_inverse(e_bob, phi_bob)
print(d_bob)

"""
Explanation: Bob then picks $e = 23$, which is relatively prime to 1260.
He finds the modular inverse of $e$ modulo $(p - 1)(q - 1)$.
End of explanation
"""


c = pow(m, e_bob, n_bob)
print(c)
enc_sig = pow(sig_c, e_bob, n_bob)
print(enc_sig)

"""
Explanation: So Alice will send her signature of $M = 314$, and send it along with $M$ encrypted with Bob's public key:
End of explanation
"""


dec_c = pow(c, d_bob, n_bob)
print(dec_c)
dec_sig = pow(enc_sig, d_bob, n_bob)
print(dec_sig)

"""
Explanation: Bob can now decrypt the message and the signature using his private key:
End of explanation
"""


pow(dec_sig, e_alice, n_alice) == m

"""
Explanation: This is equal to what he will get by verifying the signature:
End of explanation
"""


e = 65537

"""
Explanation: Up to this point we have been using small numbers, but in reality we use much bigger ones.
For instance, we want the sizes of our RSA keys to be 4096 bits.
Let's see how RSA works with such numbers.
In what follows we did not pulled big numbers out of thin air. In reality, we used the OpenSSL toolkit, in case you wonder how the example was built.
We'll use $e = 65537$.
End of explanation
"""


p = 0x00cfb0f468a68aee13806191c962ea\
565a4ab0d5547797d05a27aac67d6a\
ba1b279a1e7f62220b26190cefb271\
5d4bb81e28cffc290c2c05a58c9767\
184ceec95e3b333833829e346ec9ec\
f50ba2ba033f88d5b961008726f61b\
7600fd6b0d408c2d347ab8360aa14c\
eb9b4c851e61b76265bf53b510c647\
d185341571cb8fa76e1fce322906a8\
8a78fb4c588d821a08d395dc57e972\
2cc83c71cf3a138531f3e0f3918996\
eaf80c4879bf94755f0d2f470d5d6f\
bcbe1ec71fa2012341dcf8be36daf2\
3f3b00d30859a373efce255649602d\
f7664779bdc441602d3f0217240003\
a96801730aba5392796d0ea69116e8\
2e107d48b35d010c3c4a49973b3aa7\
d047

"""
Explanation: We need two large primes $p$ and $q$, so here is $p$:
End of explanation
"""


q = 0x00c7e596a9d7d1ee5f7e591933b3b9\
9f8e720b9f3e7b402987adb9480595\
14a5bd56d071bb9ef8637cd9c34932\
1d60ff2990bf2d4d1178d6456d7007\
ae527e3f8d7128a4f0d7fe04179b2a\
080c7c63f85207be1e21a8d322823a\
201860accf874effbc9a14bfeb266c\
83bf2957dc79f1459a34d7bda13b96\
caa239540b9337c018793d0645bf4c\
541e792bccfb43b849505296da74c9\
18ae9b47dbc544ac880baaf733df5d\
76fd0a2bfb9c9b2bfe24393a61acdb\
2cc134366ce669788ff8c85ac4806a\
b35bc8d1110a27769fabae1a474007\
33f0e63e078b15163a86b7f402d9e4\
644a594f2e42b095728d25d411eb0a\
72efe859f58e5bdd1f93d15b77fb90\
c9dd

"""
Explanation: And here is $q$:
End of explanation
"""


phi = (p - 1) * (q - 1)
print(hex(phi))

"""
Explanation: Now we can calculate $(p - 1)(q - 1)$:
End of explanation
"""


n = p * q
print(hex(n))

"""
Explanation: And we can also calculate $n = pq$:
End of explanation
"""


d = modular_inverse(e, phi)
print(hex(d))

"""
Explanation: The public key is $(e, n)$.
The private key is $(d, n)$ where $d$ is the multiplicative inverse modulo $(p - 1)(q - 1)$ of $e$.
That is:
End of explanation
"""


encoded_m = int.from_bytes('ATTACKATDAWN'.encode('utf-8'), byteorder='big')
print(m)

"""
Explanation: Let's encrypt the message ATTACKATDAWN. 
To do that, we need to convert the message to a number smaller than $n$.
One way to do that is to convert the string to a sequence of bytes and then interpret that sequence of bytes as an integer, using the int.from_bytes() function that we saw in the notebook for Chapter 4.
End of explanation
"""


c = pow(encoded_m, e, n)
print(c)

"""
Explanation: The number is well below $n$, so we are fine.
We can encrypt it:
End of explanation
"""


dec_c = pow(c, d, n)
dec_c == encoded_m

"""
Explanation: And we can verify that it decrypts correctly:
End of explanation
"""


decoded_m = dec_c.to_bytes((dec_c.bit_length() + 7) // 8, byteorder='big').decode('utf-8')
print(decoded_m)

"""
Explanation: Finally, we can recover the original string, by converting its number encoding to a series of bytes, and that to a string.
Note that the int.to_bytes() function requires the length of the byte array, which we calculate as we go.
In effect, we add 7 to the number of bits representing the integer encoding of the message, and then we perform an integer division by 8. In this way we get the rounded up multiple of 8, which is what we want.
End of explanation
"""


import string

for lc, uc in zip(string.ascii_lowercase, string.ascii_uppercase):
    bin_lc = bin(ord(lc))
    bin_uc = bin(ord(uc))
    diff = ord(lc) ^ ord(uc)
    print(lc, bin_lc, uc, bin_uc, bin(diff), diff)

"""
Explanation: Note, though, that if our message cannot be encoded with less bits than those required for representing $n$, the modulo, we cannot encrypt it using RSA.
In that case, we use RSA only to exchange a secret encryption key that we will use to encrypt and decrypt our message using a symmetric encryption algorithm, such as AES, using a hybrid encryption scheme: a combination of symmetric and asymmetric cryptography.
Message Hashing
If we want to sign a large message, we usually sign a digital fingerprint of the message instead.
A  fingerprint of a message $M$ is a short piece of identifying data that we get by applying a special fast function $h(M)$ to the message. 
This function is called a hash function.
As a hash function maps a message of a number of bits to a digest of a smaller number of bits, we will always have collisions: different messages hashing to the same value.
However, a good hash function will make such collisions very unlikely in practice.
A good family of hash function is the Secure Hash Algorithm 2 (SHA-2) family of functions, defined as part of the Secure Hash Standard.
The functions are available in Python through the hashlib library.
As an example, we will use SHA-256, which produces 256 bit hashes.
We can verify that even very similar messages produce very different hashes.
For example, capital and smaller case latin letters differ only by one bit, bit 100000 = 32 as we can see below:
End of explanation
"""


import hashlib

print(hashlib.sha256(b"i am going to be hashed").hexdigest())
print(hashlib.sha256(b"I am going to be hashed").hexdigest())

"""
Explanation: We can then see what happens if we get the SHA-256 hash value of i am going to be hashed vs. the hash value of I am going to be hashed.
The two messages differ by just one bit.
Yet they produce completely different SHA-256 hash values.
End of explanation
"""


