### Euler–Fermat-tétel és RSA
### =========================


### ---------------------------------------------------------------------------
### 1. feladat: Invertálható számok
###
### Adott m-re adjuk vissza az invertálható számok listáját 0-tól m-1-ig.

def invertibles (m):
    pass #TODO

def test1 ():
    print("1. Invertálhatók")
    for m in range(1, 11):
        L = invertibles(m)
        if L != None: print(f"m={m}: {L}, len={len(L)}")
    print()
#test1()


### ---------------------------------------------------------------------------
### 2. feladat: Euler-féle φ-függvény

### a) Számítsuk ki φ(n)-et ("phi(n)") a definíció alapján.
def phi_def (n):
    pass #TODO

### b) Számítsuk ki φ(n)-et ("phi(n)") a prímtényezős felbontás alapján.
def phi_fac (n):
    pass #TODO

### c) Van-e olyan n >= 3, amelyre φ(n) ("phi(n)") páratlan?
### Írjuk ki az összes ilyet n=1000-ig. (A függvény ne adjon vissza semmit.)
### Vajon mivel magyarázható az eredmény?
def odd_phis ():
    pass #TODO

def test2 ():
    print("2. Euler-függvény")
    for n in range(1, 11):
        print(f"phi({n}) = {phi_def(n)} = {phi_fac(n)}")
    if phi_def(2) != None:
        for n in range(1, 101):
            assert phi_def(n) == euler_phi(n), f"phi_def({n})"
        print("phi_def() OK")
    if phi_fac(2) != None:
        for n in range(1, 101):
            assert phi_fac(n) == euler_phi(n), f"phi_fac({n})"
        print("phi_fac() OK")
    odd_phis()
    print()
#test2()


### ---------------------------------------------------------------------------
### 3. feladat: RSA implementálása

### a) Generáljunk egy RSA-kulcspárt.
### L: a prímek L-nél kisebb véletlen prímszámok legyenek.
### Visszatérési érték: (pk, sk), ahol pk a nyilvános kulcs, és sk a titkos
### kulcs (mindkettő maga is egy-egy pár, tehát összesen négy érték lesz).
### A nyilvános kitevő legyen az első olyan páratlan szám, amely megfelel az
### RSA feltételeinek.
### (Egyik alfeladatban se használjunk olyan műveletet, amely az RSA feltörését
### igényelné, pl. n faktorizálását.)
def rsa_generate (L):
    pass #TODO

### b) Titkosítsunk a bemenő m üzenetet a nyilvános kulcs segítségével.
def rsa_encrypt (m, pk):
    n,e = pk
    pass #TODO

### c) Állítsuk vissza a titkosított c értékből az m üzenetet a titkos kulcs
### segítségével.
def rsa_decrypt (c, sk):
    n,d = sk
    pass #TODO

def test3 ():
    print("3. RSA")
    for L,m in [
        (10000, 123456),
        (2^150, 1234567890123456789),
    ]:
        pk, sk = rsa_generate(L)
        print("pk =", pk)
        print("sk =", sk)
        c = rsa_encrypt(m, pk)
        if c == None: break
        print("üzenet: m =", m)
        print("titkos: c =", c)
        mm = rsa_decrypt(c, sk)
        if mm == None: break
        print("vissza: m =", mm)
        assert mm == m % pk[0]
    print()
#test3()


### ---------------------------------------------------------------------------
### 4. feladat: RSA feltörése
###
### Törjük fel az RSA-t a factor() függvény segítségével. (Ez nyilván csak kis
### számokra fog működni.) A függvény bemenete a nyilvános kulcs (pk) és a
### titkosított szöveg (c), és visszaadja a megfejtett nyílt szöveget (m).
### (Tipp: először állítsuk vissza a titkos kulcsot.)

def break_rsa (pk, c):
    pass #TODO

def test4 ():
    print("4. RSA feltörése")
    pk = (1381729, 17)
    c = 1233745
    m = break_rsa(pk, c)
    print("c =", c)
    print("m =", m)
    print()
#test4()


### ---------------------------------------------------------------------------
### 5. feladat: Carmichael-féle λ-függvény
###
### Az Euler–Fermat-tétel szerint megfelelő a-kra
###     a^φ(m) ≡ 1 (mod m).
### De φ(m) nem feltétlenül a legkorábbi ilyen kitevő. Például m = 8 esetén
### a megfelelő alapok 1,3,5,7, és:
###     1^2 ≡ 1 (8),  3^2 ≡ 1 (8),  5^2 ≡ 1 (8),  7^2 ≡ 1 (8),
### azaz a φ(8) = 4 kitevő helyett már 2-re is teljesülne a tétel.
### A Carmichael-féle λ-függvény (λ = "lambda") a lehető legkisebb "jó" kitevőt
### jelenti, azaz λ(n) a legkisebb olyan k kitevő, melyre a^k ≡ 1 (mod n)
### minden olyan a-ra, amelyre az Euler–Fermat-tétel feltétele teljesül.
### Megjegyzés: λ(n) | φ(n), és sok esetben meg is egyeznek.
### Megjegyzés 2: az RSA-ban φ(n) helyett gyakran inkább λ(n)-t használnak.
### Lásd még: https://en.wikipedia.org/wiki/Carmichael_function

### a) Számítsuk ki λ(n)-et ("lambda(n)") a fenti definíció alapján.
def lambda_def (n):
    pass #TODO

### b) A Carmichael-féle λ-függvényre is van egy olyan rekurzió, mint φ(n)-re:
###    1. Ha p prím, akkor λ(p) = φ(p) = p-1.
###    2. Ha p páratlan prím, akkor λ(p^k) = φ(p^k) = (p-1)*p^(k-1).
###    3. Ha p = 2 és k <= 2, akkor λ(p^k) = φ(p^k) = (p-1)*p^(k-1) = 2^(k-1).
###    4. Ha p = 2 és k >= 3, akkor λ(p^k) = φ(p^k)/2 = (p-1)*p^(k-1)/2 = 2^(k-2).
###    5. Ha a és b relatív prím, akkor λ(a, b) = lkkt(λ(a), λ(b)).
### Számítsuk ki ezen szabályok segítségével λ(n)-et az n prímtényezős
### felbontásából (hasonlóan, mint φ(n)-et fent).
def lambda_fac (n):
    pass #TODO

def test5 ():
    print("5. Lambda-függvény")
    for n in range(1, 11):
        print(f"lambda({n}) = {lambda_def(n)} = {lambda_fac(n)} (phi({n}) = {euler_phi(n)})")
    if lambda_def(2) != None:
        for n in range(1, 101):
            assert lambda_def(n) == carmichael_lambda(n), f"lambda_def({n})"
        print("lambda_def() OK")
    if lambda_fac(2) != None:
        for n in range(1, 101):
            assert lambda_fac(n) == carmichael_lambda(n), f"lambda_fac({n})"
        print("lambda_fac() OK")
    print()
#test5()