pip install asymmetric-encryption

cd .\test\
python -m unittest discover 

==============================================
                   Generate
----------------------------------------------
let p and q be prime numbers
let n = p * q
let tot(n) = (p - 1) * (q - 1)
let e be prime number such that 2 < e < tot_n -1 and gcd(e, tot_n) == 1
let d = e**-1 % tot_n
        |
        ⌄
It took me ages to figure out what that means.
Basically if you do e * d and then mod it by tot_n you get 1.
e and d must be inteager primes.
For example:
p = 5 // Prime should be a lot larger this is for example. 
q = 7 // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
n = 35 // p * q, 5 * 7 = 35
tot_n = 24 // (p - 1) * (q - 1), (5 - 1) * (7 - 1) = 4 * 6 = 24
e = 5 // greatest common denemenator between tot_n and e is 1
(e * d) % tot_n = 1
d = 5 // 5 * 5 = 25, 25 % 24 is 1


Public: e, n
Private: p, q, tot_n, d
==============================================
                   Encryption
----------------------------------------------
c = m**e % n
==============================================
                   Decryption
----------------------------------------------
m = c**d % n
==============================================
                   Signature
----------------------------------------------
s = m**d % n
==============================================
                    Verify 
----------------------------------------------
v = s**e % n
m == v
==============================================

from AsymmetricEncryptions import RSA, RSAKey

priv, pub = RSA.generate_key_pair(1024)
priv.export(file_name="file_name.txt", pwd=b"test")
RSAKey.load(file_name="file_name.txt", pwd=b"test")
# load will throw an assertion error if the HMACs aren't the same

                        The math of ElGamal
------------------------------------------------------------------------

                          Key Generation
------------------------------------------------------------------------
Let p = large prime number
Let g = 1 < g < p-1
Let x = 1 < x < p-1
Let y = g**x % p

Public = {p,g,y}
Private = {x}

                            Encryption
------------------------------------------------------------------------

m = message < p
Let b = 2 < b < p-1
C1 = g**b % p
C2 = (m * y**b) % p

                            Decryption
------------------------------------------------------------------------

XM = C1**x % p
m = (C2 * XM**(p-2)) % p

                             Signing
------------------------------------------------------------------------
m = message
k = 0 < k < p
s1 = g**k % p
phi = p - 1
mod_inv = k ** -1 % phi // pow(k, -1, phi) or mod_inv*k % phi == 1
s2 = (mod_inv * (hash(m) - x * s1)) % phi

Send {m, s1, s2}
Keep k private

                             Verifying
------------------------------------------------------------------------
V = y**s1 * s1**s2 % p
W = g**hash(m) % p
If V == W then the message was signed by the private key



                              Example
------------------------------------------------------------------------

Let p = 23
Let g = 6
Let x = 8
Let y = 6**8 % 23 = 18

m = 4
Let b = 3
C1 = 6**3 % 23 = 9
C2 = (4 * 18**3) % 23 = 6

XM = 9**8 % 23 = 13
m = (6 * 13**21) % 23 = 4

Sign 
m = 5
k = 3
s1 = g**k % m = 9
phi_n = p-1 = 22
inv = k**-1 % phi_n = 15
s2 = (inv * (m - x * s1)) % phi_n = 7

Verify
V = (18**9 * 9**7) % 23 = 2
W = 6**5 % 23 = 2

The message is authentic

from AsymmetricEncryptions import ElGamalKey, ElGamal

priv, pub = ElGamal.generate_key_pair(1024)
priv.export(file_name="file_name.txt", pwd=b"test")
ElGamalKey.load(file_name="file_name.txt", pwd=b"test")
# load will throw an assertion error if the HMACs aren't the same

                           The math of DSA
------------------------------------------------------------------------
The math is very complex.
Good luck.
        
                            Key generation
------------------------------------------------------------------------
Key generation has two phases. 
The first phase is a choice of algorithm parameters which may be shared between different users of the system.
The second phase computes a single key pair for one user.

First phase (paramaters)
------------------------------
1. Choose an aproved hash function (I chose Sha256) H that outputs |H| bits (256)
2. Choose a key length L (1024 without any change).
(2048 or 3072 is considered safer for life long until 2030)
3. Choose modulus N such that N < L and 0 < N <= |H|
Tricky part:
4. Choose N-bit prime q
5. Choose L-bit prime p such that (p -1) % q == 0
End of tricky part.
6. Choose 0 < h < p - 2
7. Compute g = h**((p-1)//q) % p
{p, q, g} may be shared.

Second phase (Actuall key gen)
-------------------------------
1. Choose private key x such that 0 < x < q -1
2. Compute public key y, y = g**x % p

                            Signing
------------------------------------------------------------------------
m = message as an int
1. Choose an integer k randomly from {1... q-1}
2. Compute r = (g**k % p) % q
3. Compute s = ((k**-1 % q) * (H(m) + x * r)) % q
4. If s == 0 or r == 0: start over with a different k
Sig = (r, s)
                            Verifying
------------------------------------------------------------------------
m = message as an int
1. Verify that 0 < r < q, 0 < s < q
2. Compute W = s**-1 % q
3. Compute U1 = (H(m) * w) % q
4. Compute U2 = (r * w) % q
5. Compute V = (((g**u1 % p) * (y**u2 % p)) % p) % q
The signature is valid if and only if V == r
------------------------------------------------------------------------
                                
                                
                                Example
------------------------------------------------------------------------
// key param gen
p, q = 11, 5 // (p -1) % q == 0
h = 8
g = 8**2 % 11 = 9
{11, 5, 9}
// make a key
x = 7
y = 9**7 % 11 = 4

// sign
m = 3
H(M) = 7
k = 2
r = (9**2 % 11) % 5 = 4
s = ((2**-1 % 5) * (7 + 7 * 4)) % 5 = (3 * 56) % 5 = 3
{r = 4, s = 3}

// verify
m = 3
H(M) = 7
W = 3**-1 % 5 = 2
U1 = (7 * 2) % 5 = 4
U2 = (4 * 2) % 5 = 3
V = (((5 ** 4 % 11) *  (4 ** 3 % 11)) % 11) % 5 = 4

V == r -> the message is authentic

Key Gen
-----------

x = random int
y = G * x
Private: {x}
Public: {y}

ECDH
-----------
Ax, AY
Bx, By

Alice shared key:
Ax * By
Bob shared key:
Bx * AY


Encryption
-------------
You can't just encrypt with ECC but you can make an hybrid scheme (ECIES).

r = random
R = G * r
S = Y * r
sk = KDF(S)
c = Encrypt(msg, sk)
send c, R

Decryption
------------
s = R * x
sk = KDF(s)
msg = Decrypt(c, sk)

# key gen
let n be a large prime
let g < n - 1
let x < n - 1 
let y = g**x % n
Private: {x}, Public: {n, g, y}
# encryption
{E(m, S) -> symmetric encryption function, m}
let r be a random value
let R = g**r % n
let S = y**r % n
let E = E(m, S)
ciphertxt: (E, R)

# decryption
{D(m, S) -> corresponding decryption function, (E, R)}
S = R**x % n
m = D(E, S)

First define a vector S this will be your private key then we need to define A.
A is a group of random vectors that contain random numbers up to a prime number q.
Then we define E (the errors in Learning With Errors).

E contains numbers between 1-4 including 1 and 4. 

A helper function is this: 
def helper(list, s):
    return sum([(s[i] * list[i]) % q for i in range(len(list))])

Now we can use our variables to define B using this formula: B[i] = helper(A, S) + E[i] (mod q)

So for example A={{80, 5, 6}, {86, 19, 17}...}, S={5, 2, 4}, Q=97 E={3,3,4...}

So B1 will be equal to (80 * 5) + (5 * 2) + (6 * 4) + 3 (mod 97) = 49.

To encrypt a bit (m in [0, 1]) we define u and v 


def sum_u(l) -> list[int]:
    result_arr: list[int] = [0] * len(l[0])
    for i in range(len(l)):
        for c in range(len(result_arr)):
            result_arr[c] += l[i][c]
    return result_arr
    
The sum_u function sums everything in a list[list] into a list[]
For example:
l = [[10, 20], [50, 30], [10, 20]]
So the answer of sum_u(l) is [70, 70]

u = sum_u(A samples)
v = (sum(B samples) - Q÷2 * M) % q

To decrypt we take v and u to this formula dec = v - helper(u, s) (mod q)
If dec is less than q ÷ 2 then M=0
If dec is more then q ÷ 2 then M=1

This isn't gurrenteed to work 100% of the time!

Alice and Bob publicly agree on p (large prime) and g (g < p)


|        Alice       |        Public       |        Bob       |     
----------------------------------------------------------------
|      {a, g, p}     |     g, p            |      {b, g, p}   |
|                    |                     |                  |
|     A = g**a % p   |   A ----------->    |     k = A**b % p |
|                    |                     |                  |
|   k = A**b % p     |     <----------- B  |     B = g**b % p |
|                    |                     |                  |
----------------------------------------------------------------
k is the shared symmetric secret.
g**a**b % p == g**(a * b) % p

Sign
Private key: x
Public key: y = G * x
e = H(m)
k = secure random < curve.n
K = G * k
r = K.x
s = (k**-1 * (e + r * x)) % n
send r, s

Verify
Public key: y = G * x
r, s
m

e = H(m)
u1 = (e * s**-1) % n
u2 = (r * s**-1) % n
w = G * u1 + y * u2
if w.x == r then the signature is valid

Nonce reuse private key leakage!:
if r1 == r2 and (s1 != s2 or m1 != m2)
k = (e1 - e2) * ((s1 - s2)**-1) 
k = k % n
x = (s1 * k - e) * r1**-1
x = x%n
x is the private key

Signing:
Get a list of public RSA keys (the group of keys).
Randomly insert your private key in the list (Don't put it first or last), will call this possiton z.
To sign a message m:
permute a hash fanction E to take x, and return hash(x + m).
Get a random glue value u.
For each key other than your's have a random number, this will act as some fake key, put it in array s.
c = v = E(u)
G(x, e, n) = x**e % n
For i, key in enumerate(keys):
    if i == z: continue
    v = E(G(s[i], key.e, key.n) ^ v)
then
s[z] = G(v ^ u, keys[z].d, keys[z].n])
rk = keys.copy()
rk[z] = rk[z].get_pub()
send the message, c, s, rk
RK is the public keys denoting the group members
s is the fake private keys with the one we calculated

Verifing:
Permute a hash fanction E to take x, and return hash(x + m).
v = c
For i, key in enumerate(keys):
    v = E(G(s[i], rk[i].e, rk[i].n) ^ v)
if v == c: then it's verified

The math of the AOS ring signature is building a ring such that it loops when calling a trap door function that uses the public keys.

Lets assume we have a group of public key, let's call them keys. And at the jth position there's the signer's key.
It's importent to note that the keys should be shuffled and should have no order, so the signers key wouldn't be infront or be last.
Signing:

We pick a random number alpha

Q = G * alpha

Where G is the curve generator point

We say that e[j+1] = H(Q) where H is a cryptographic hash function that was permuted to append the message M.
(H for example: sha256(M || m))

Then, i, starting at j + 1 until we get back to j exlclusive. (i is mod the length of the keys). We do:
s[i] = 2 < random < curve.n
e[i + 1] = H(s[i] * G + e[i] * keys[i])

And finaly at j
we do:
s[j] = (alpha - e[j] * x) mod curve.n
where x is the private key
the signature is then (e[0], s[0], s[1]... s[j].. s[len(keys)-1])
And the public keys should be in order.
Verify:
e = e_0 = signature[0]

For key in keys:
    e = H(s[i] * G + e * keys[i])
if e == e_0 then the signature passes

Why this works?

I had a pretty hard time understanding why this works but it's actually pretty simple.

We firstly "seed" the ring at the next key of j to be H(alhpa * G).
so Q = alhpa * G

The ring then takes the form:
H(s[i] * G + e[i] * keys[i])
Where s[i] is a random number and e[i] is the last e.
Then we reach ourself, at position j, and s[j] takes this form:
(alpha - e * x) mod curve.n
This is essentiely "going back in time" to find e at j + 1
And if you look at the formula to calculate e the terms cancle eachother out.

s[j] * G + e * keys[j] =
(alpha - (e * x)) mod curve.n * e * x * G = 
alpha * G = Q
So essentiely we went back in time and found the formula to seed out first e

O-ptimal
A-symmetric
E-ncryption
P-adding

G(x) |
     | -> hash functions outputing g and h bits
H(H) |

Pad
================================
r -> random nonce of g bits
m = m || 0**(g-len(m))
x = m ^ G(r)
y = H(X) ^ r
p =  x || y
remember that x and y are g and h bits long
--------------------------------
Unpad
================================
x = p[:g]
y = p[g:]
r = H(X) ^ y
m = x ^ G(r)

Shamir's Secret Sharing
---------------------------
n -> the number of shares
t (k in the video above) -> the number of people needed to find the answer

Take your secret as m.
Place m on a graph such that the point is (0, m).

Generate a polynomial with a0 being m. Like this for example (3 degree polynomial):
y = a0 + a1*x + a2*x**2 + a3*x**3


Generate n points on the polynomial and share them. (x != 0 of course)
-----------------------------
To find m back you need to calculate the formula again, which you can do that with t shares.
And then plug 0 into the formula and you get m.

Better m finding method
------------------------
Since we only need to calculate a0 there is and easier formula:

a0 = 0
foreach xj, yj in the points:
    prod = 1
    foreach xi, yi in the points:
        if xi == xj: continue
        prod *= xi/(xi-xj)
    prod *= yj
    a0 + prod
    
Example:
------------------------------
n = 4
t = 2

m = 3
a1 = 4 
y = 4x + 3
random point on the line number 1: x = 4, y = 16
random point on the line number 2: x = 6, y = 27
random point on the line number 3: x = 2, y = 11
random point on the line number 4: x = 1, y = 7


|
|
|
|
|                               (6, 27)
|
|               (4, 16)
|
|          (2, 11)                         
|   
|       (1, 7)
|
(0; 3)
|
|
0------------------------------------------

Given only one of those points it's impossible to find m.
However, given t points you can always find m again.

let's say that we got both points (1, 7) and (6, 27).
slope = (27 - 7) / (6 - 1) = 20 / 5 = 4
Using the formula y = m(x - x1) + y1 we get:
y = 4x - 4 + 7, y = 4x + 3.
Pluge x = 0 and we get our answer: m = 3.

__init__(prime) -> supply another prime

SSS().make_random_shares -> returns a list of cordinets as a tuple: list[tuple[int, int]]
secret: the secret
shares: number of shares to generate
minimum: the number of shares needed to reconstruct the secret

SSS().reconstruct_secret(shares) -> returns the secret
shares: the shares needed to reconstruct the secret

Allows you to share one public share and memorize a few words to be used as a key sharing scheme

---------------------------------------------------
Lets say Alice want to prove Bob that she know a password without reveling any information about it.
Alice and Bob agree on a generator g and a prime n such that g < n

Alice:
x = Hash(Password)
y = g**x % n
v < n
t = g**v % n

Alice sends to Bob: {y, t}

Bob:
Bob generates a number c such that c < n
Bob sends Alice: {c}

Alice:
r = v - c * x
Alice sends Bob: {r}

Bob:
z = (g**r * y**c) % n
verified if z == t
---------------------------------------------------
Example:
g = 35
n = 53

Alice:
x = 17
y = 35**17 % 53 = 20
v = 7
t = 35**7 % 53 = 34
{y = 20, t = 34}

Bob:
c = 15
{c = 15}

Alice:
r = 7 - 15 * 17 = -248
{r = -248}

Bob:
z = ((35**-248) * (20**15)) % 53 = 34
t == z = 34 -> verified

# Alice
1. Alice has two messages: {m0, m1} and wants to send exactly one of them to Bob. Bob does not want Alice to know which one he receives.
2. Alice generates an RSA key pair {e, n, d: keep private}
3. She also generates two random values, {x0, x1} and sends them to Bob along with her public RSA key.
# Bob gets e, n, x0, x1
4. Bob picks b to be 0 or 1 (b is what message he will get) and selects xb
5. Bob generate a random value k (k < n) and computes:
v = (xb - k**e) % n
Bob sends to Alice: {v} and keeps {b, k} a secret.
# Alice gets: {v}
6. Alice computes:
k0 = (v - x0)**d % n
k1 = (v - x1)**d % n
7. 
mp0 = (m0 + k0) % n
mp1 = (m1 + k1) % n
Alice sends Bob: {mp0, mp1}
# Bob
mb = (mpb - k) % n
mb == the message that bob chose.

let keyA be a key to a symmetric encryption function EA and decryption function DA
let keyB be a key to a symmetric encryption function EB and decryption function DB

c1 = EA(m, keyA)
# Pass to Bob
c2 = EB(c1, keyB)
# Pass to Alice
c3 = DA(c2, keyA)
# Pass to Bob
m = DB(c2, keyB)

Construct a new discret log key (n -> prime, g -> generator, x -> m, y = g**x % n).
r -> random value
t = g ** r % n
c = Hash(g | y | t)
s = r + c * x
send {t, s, new_key.public}
# verify
c = Hash(g | y | t)
if g**s % n == (t * y**c) % n: the proof is true

Kerberos (/ˈkɜːrbərɒs/) is a computer-network authentication protocol that works on the basis of tickets to allow nodes communicating over a non-secure network to prove their identity to one another in a secure manner. 
Its designers aimed it primarily at a client–server model, and it provides mutual authentication—both the user and the server verify each other's identity. 
Kerberos protocol messages are protected against eavesdropping and replay attacks.

We want to calculate the sum of two numbers A and B
PA only knows A
PB only knows B

PA splits A into 2 shares: a1 and a2 such that a1 + a2 = A
PB splits B into 2 shares: b1 and b2 such that b1 + b2 = B

PA sends to PB a2
PB sends to PA b1

PA does a1 + b1 = s1
PB does a2 + b2 = s2
s1 + s2 = A + B

   PA   |  PB
----|---------------
A   =    a1    |  a2
+   |    +     |  +
B   =    b1    |  b2 
=   ---------------
s   =   s1   +   s2
    

Each parti flips a coin privately such that A has a shared bit with B and one with C.
B with A and C. and C with A and B. (AB = BA, AC = CA, BC = CB)
Each of the parties anounce:
If they paid: 1 ^ [shared bits[i] ^ shared bits[i + 1]
If not: [shared bits[i] ^ shared bits[i + 1]
They than XORed the anouncement. If it's 1 then someone has paid, if it's 0 then the NSA has paid
Lets go through an example.
If the NSA paid and none other:
AB = BA = 1
BC = CB = 1
AC = CA = 0
A anounces: 0 ^ 1 ^ 0 = 1
B anounces: 0 ^ 1 ^ 1 = 0
C anounces: 0 ^ 1 ^ 0 = 1
They then XOR everything together and get 0: (1 ^ 0 ^ 1 = 0) None paid
If A paid it's the same except A anounces 0:
A anounces: 1 ^ 1 ^ 0 = 0
B anounces: 0 ^ 1 ^ 1 = 0
C anounces: 0 ^ 1 ^ 0 = 1
They then XOR everything together and get 1: (1 ^ 0 ^ 0 = 1) Someone paid

The protocol assumes that one (And only one) party has paid.
This is because of the xors cancelling eachother.

    A   |   B   |   C
------------------------------------
A   0   |   1   |   0
------------------------------------
B   1   |   0   |   1
------------------------------------
C   0   |   1   |   0

Notice how this is symmetric. 
If none has paid than the number of ones must be even and so they cancel out.
Now this is the same thing but now A has paid:
    A   |   B   |   C
------------------------------------
A   1   |   1   |   0
------------------------------------
B   1   |   0   |   1
------------------------------------
C   0   |   1   |   0
There is an odd number of ones, so the answer will be 1.
B and A paid.
    A   |   B   |   C
------------------------------------
A   1   |   1   |   0
------------------------------------
B   1   |   1   |   1
------------------------------------
C   0   |   1   |   0
There is another one so they'll cancell eachother out. Leading into a false negative of 0. 
C thinks that nobody paid, but A and B will know what has happend.
    A   |   B   |   C
------------------------------------
A   1   |   1   |   0
------------------------------------
B   1   |   1   |   1
------------------------------------
C   0   |   1   |   1
If everyone pays (i.e and odd number of ones) the answer will be 1 again, but everybody will think that they paid. 
Thus nobody will suspect that they paid three times.