### Euler's totient and RSA
### =======================


### ---------------------------------------------------------------------------
### Exercise 1: Invertible numbers
###
### Return the list of invertible numbers modulo m, between 0 and m-1.

def invertibles (m):
    pass #TODO

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


### ---------------------------------------------------------------------------
### Exercise 2: Euler's totient

### a) Calculate φ(n) ("phi(n)") using the definition.
def phi_def (n):
    pass #TODO

### b) Calculate φ(n) ("phi(n)") from the prime factorization.
def phi_fac (n):
    pass #TODO

### c) Is there any n >= 3 for which φ(n) ("phi(n)") is odd?
### Print all such numbers up to n=1000. (Don't return anything.)
### Can you explain the result?
def odd_phis ():
    pass #TODO

def test2 ():
    print("2. Euler's totient")
    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()


### ---------------------------------------------------------------------------
### Exercise 3: Implement RSA

### a) Generate an RSA key pair.
### L: the upper bound of the random prime numbers.
### Return value: (pk, sk), where pk is the public key, and sk is the private
### key (both of which are themselves pairs, i.e. there are 4 values in total).
### Generate the public exponent by finding the first odd number that satisfies
### the criteria of RSA.
### (Don't use any operation that would require breaking RSA, e.g. factoring.)
def rsa_generate (L):
    pass #TODO

### b) Encrypt the given plaintext message m using the public key.
def rsa_encrypt (m, pk):
    n,e = pk
    pass #TODO

### c) Decrypt the given ciphertext c using the private key,
### i.e. restore the original m.
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("plaintext:  m =", m)
        print("ciphertext: c =", c)
        mm = rsa_decrypt(c, sk)
        if mm == None: break
        print("decrypted:  m =", mm)
        assert mm == m % pk[0]
    print()
#test3()


### ---------------------------------------------------------------------------
### Exercise 4: Break RSA
###
### Break RSA using the factor() function. (Of course, this will work only for
### small numbers.) The function receives the public key (pk) and the
### ciphertext (c), and returns the recovered plaintext message (m).
### (Hint: first recover the secret key.)

def break_rsa (pk, c):
    pass #TODO

def test4 ():
    print("4. Break RSA")
    pk = (1381729, 17)
    c = 1233745
    m = break_rsa(pk, c)
    print("c =", c)
    print("m =", m)
    print()
#test4()


### ---------------------------------------------------------------------------
### 5. feladat: Carmichael's λ function
###
### Euler's totient function says that for suitable bases,
###     a^φ(m) ≡ 1 (mod m).
### But φ(m) is not necessarily the smallest such exponent. For example, for
### m = 8, the suitable bases are a=1,3,5,7, and:
###     1^2 ≡ 1 (8),  3^2 ≡ 1 (8),  5^2 ≡ 1 (8),  7^2 ≡ 1 (8),
### i.e. instead of φ(8) = 4, the exponent 2 would also satisfy the theorem.
### Carmichael's λ function (λ = "lambda") means the smallest possible "good"
### exponent, i.e. λ(n) is the smallest exponent k for which a^k ≡ 1 (mod n)
### is true for all base 'a' that is suitable for Euler's totient function.
### Note: λ(n) | φ(n), and they are often equal.
### Note 2: in practice, implementations of RSA often use λ(n) instead of φ(n).
### See also: https://en.wikipedia.org/wiki/Carmichael_function

### a) Calculate λ(n) ("lambda(n)") using the above definition.
def lambda_def (n):
    pass #TODO

### b) Carmichael's λ function has a similar recursion to φ(n):
###    1. If p is prime, then λ(p) = φ(p) = p-1.
###    2. If p is an odd prime, then λ(p^k) = φ(p^k) = (p-1)*p^(k-1).
###    3. If p = 2 and k <= 2, then λ(p^k) = φ(p^k) = (p-1)*p^(k-1) = 2^(k-1).
###    4. If p = 2 and k >= 3, then λ(p^k) = φ(p^k)/2 = (p-1)*p^(k-1)/2 = 2^(k-2).
###    5. If a and b are coprime, then λ(a, b) = lcm(λ(a), λ(b)).
### b) Calculate λ(n) from the prime factorization of n, using these rules
### (similarly to φ(n) above).
def lambda_fac (n):
    pass #TODO

def test5 ():
    print("5. Lambda function")
    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()