Multi-prime RSAを復号してみる（Hack The Vote 2016 The Best RSA） - ももいろテクノロジー

この記事は「CTF Advent Calendar 2016」9日目の記事です。 RSA暗号は二つの素数p, qから計算されるn=p*qを公開鍵として暗号化を行うものであるが、これを一般化したものとしてMulti-prime RSAがある。 ここでは、Multi-prime RSAの概要を説明し、これを題材にした問題を紹介する。 Multi-prime RSA RSA暗号は、二つの素数p, qとある条件を満たす整数eを用いて、次のような式をもとに計算される。 n = p * q phi(n) = (p-1) * (q-1) d = e^(-1) mod phi(n) c = m^e mod n m = c^d mod n mは平文、cは暗号文を表し、公開鍵はnおよびe、秘密鍵はdである。 また、phi(n)はオイラーのトーシェント関数と呼ばれる関数であり、nと互いに素となるn以下の自然数の