Cryptopals zestaw 5 ćwiczenie 33

Zaczynamy nowy, piąty już, zestaw ćwiczeń i na pierwszy ognień dostajemy zadanie rozgrzewkowe. Właściwie nie potrzebujemy w ogóle myśleć tylko postępować zgodnie z krokami podanymi przez autorów, ale jeżeli zatrzymamy się na chwilę i zastanowimy to dotrze do nas co się właściwie stało. A stanie się coś bardzo ciekawego co bardzo łatwo można przeoczyć.

1. Na początku wybieramy sobie jakąś liczbę pierwszą (https://pl.wikipedia.org/wiki/Liczba_pierwsza) p i podstawę g. Wartości p i g są publiczne – ich wartość nie jest tajemnicą.
2. Następnie losujemy dwie liczby a oraz b mniejsze niż p.
3. Generujemy liczby A i B tak, że A = g^a % p oraz B = g^b % p. Wartości A i B to nasze klucze publiczne – możemy je swobodnie przesyłać i każdy może poznać ich wartość.
4. Następnie generujemy klucz sesji s = A^b % p oraz s = B^a % p. Klucz s jest generowany lokalnie po stronie a i po stronie b a jego wartość w obydwu przypadkach jest taka sama.

I to jest całe ćwiczenie (oczywiście warto pamiętać o radzie autorów zadania, żeby zastosować funkcję modexp, co znacznie przyśpieszy wykonanie działań na dużych liczbach podanych w zadaniu). To co jest najciekawsze a co mogło nam umknąć to dowód albo przyczyna dlaczego to w ogóle działa, tzn. dlaczego:

A^b % p = B^a % p

Wiemy, że A = g^a %p a B = g^b % p, czyli możemy zapisać to równanie w takiej postaci:

(g^a)^b % p = (g^b)^a % p

Jak widać dowód jest banalnie prosty i opiera się na zagadnieniach o których uczą się dzieci w szkole podstawowej.

Moja implementacja:

def power_mod(b, e, m):
    " Without using builtin function "
    x = 1
    while e > 0:
        b, e, x = (
            b * b % m,
            e // 2,
            b * x % m if e % 2 else x
        )
 
    return x

def s5challenge33():
    print("Challenge 33")
    p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
    g = 2
    a = random.randrange(1, p) % p
    b = random.randrange(1, p) % p
    print("a: ", a)
    print("b: ", b)
    A = power_mod(g, a, p) #(g**a)%p
    B = power_mod(g, b, p)#(g**b)%p
    print("A: ", A)
    print("B: ", B)
    s1 = power_mod(B, a, p)#(B**a)%p
    s2 = power_mod(A, b, p)#(A**b)%p
    print("S1: ", s1)
    print("S2: ", s2)

Całość dostępna pod adresem https://gitlab.com/akoltys/cryptopals.