RSA_from_PublicKey_to_PrivateKey.jl

# RSA_from_PublicKey_to_PrivateKey.jl
# Julia-ohjelma murtaa RSA-salausmenetelmän julkisen avaimen n laskemalla
# sen alkulukutekijat p ja q.
# Näiden tekijöiden p ja q sekä julkisen eksponentin e avulla ohjelma
# laskee privaatin eli salaisen purkuavaimen d.
# Juhani Kaukoranta 4.9.2019
function PollardRho(n)
    x, y, p = 2, 2, 1
    f(x) = mod(x^2+1, n)
    while p == 1
        x = f(x)
        y = f(f(y))
        p = gcd(abs(x-y),n)
    end
    if p == n
        println( "Ei tekijöitä, avain alkuluku tms")
    else
        q = div(n,p)
        println("Avaimen ",n," tekijät:")
        println(p," ja ",q)
        return p,q
    end
end

# Julkinen avain n
n = parse(BigInt,"9467654010638058611")
println("Julkinen avain n = ",n)
println("Julkisen avaimen bittipituus = ",round(Int,log2(n)))
println("Julkisen avaimessa 10-järjestelmän numeroita = ",ndigits(n))

# Lasketaan julkisen avaimen alkulukutekijat p ja q
p, q = PollardRho(n)

e = 65537 # sertifioitu exponentti toimii toisena julkisena avaimena
println("Alkuluku p = ",p)
println("Alkuluku q = ",q)
println("Julkinen avain = ",n)
println("Tarkistus p*q = n = ",p*q)
println("Julkinen eksponentti e = ",e)

# Nyt meillä on julkinen eksponentti e ja avaimen alkulukutekijät p ja q
# Lasketaan näiden avulla salauksen privaatti purkuavain d
# Tarvitaan funktiot least common multiple lcm(a,b)
# ja modular inverse invmod(a,b)
# lasketaan Carmichaelin totientti lcm(p-1,q-1)
totient = lcm(p-1,q-1)
println("Carmichael's totient = ",totient)
d = invmod(e,totient)

# yhtälöstä d * e = 1 mod moduli ratkaistiin d
println("Tarkistus, onko d * e  ≡  1 (mod totient)")
println("d * e mod totient = ",mod(d*e,totient))
println("Salauksen privaatti purkuavain d = ",d)
println()