Skip to content

Instantly share code, notes, and snippets.

@h3y6e
Last active March 1, 2019 02:10
Show Gist options
  • Save h3y6e/a28b3d6e2404dde77b69386b8a0aa594 to your computer and use it in GitHub Desktop.
Save h3y6e/a28b3d6e2404dde77b69386b8a0aa594 to your computer and use it in GitHub Desktop.
RSAの攻撃手法Common Modulus AttackをJuliaで書く
# Common Modulus Attack
function commonModulusAttack(N::BigInt, e1::Int, e2::Int, c1::BigInt, c2::BigInt)::BigInt
s1, s2 = exEucild(e1, e2)
v = s1 > 0 ? c1^s1 : 1/c1^(-s1)
w = s2 > 0 ? c2^s2 : 1/c2^(-s2)
return v * w
end
# Extended Eucildean algorithm
function exEucild(e1::Int, e2::Int)
r = e1 > e2 ? [e1, e2] : [e2, e1]
x = [1, 0]
y = [0, 1]
while true
q = div(r[1], r[2])
r3 = r[1]%r[2]
r3 == 0 ? break : (r = [r[2], r3])
x = [x[2], x[1] - x[2]q]
y = [y[2], y[1] - y[2]q]
end
return e1 > e2 ? [x[2], y[2]] : [y[2], x[2]]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment