using Primes

struct PublicKey
    n::Integer
    e::Integer
end

struct PrivateKey
    n::Integer
    d::Integer
end

function gen_keys(p::Integer, q::Integer, e::Integer)
    isprime(p) || error("p must be a prime number")
    isprime(q) || error("q must be a prime number")
    e>0 || error("e must be positive")
    phi = (p-1)*(q-1)
    (g,u,v) = gcdx(e,phi)
    g == 1 || error("phi(n) and e must be coprime")
    u<0 ? d=(u%phi)+phi : d=u%phi
    n = p*q
    return PublicKey(n,e),PrivateKey(n,d)
end

function encrypt(m::Integer, k::PublicKey)
    0 <= m || error("m must be non-negative")
    m < k.n || error("m is too large")
    return powermod(m,k.e,k.n)
end

function decrypt(c::Integer, k::PrivateKey)
    0 <= c || error("c must be non-negative")
    c < k.n || error("c is too large")
    return powermod(c,k.d,k.n)
end

(pbk,pvk) = gen_keys(13,17,11)
println("The public key is (n,e)=($(pbk.n),$(pbk.e)), give it to people willing to send you a secret message!")
println("The private key is (n,d)=($(pvk.n),$(pvk.d)), don't share it!")
m = 149
println("Original message: $m")
c = encrypt(m, pbk)
println("Encrypted message: $c")
println("Decrypted message: $(decrypt(c,pvk))")