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以下の自然数の
数学 - Chinese Remainder Theorem (中国剰余定理) - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
本記事では中国剰余定理(Chinese Reminder Theorem, CRT)1について解説する. 数学的な定義や意義について触れた後, 応用例としてRSA-CRT, Multi-Prime RSA, そしてPohlig-Hellman Attackについて述べる. 前提知識として, 簡単な初等整数論・群・環の言葉を知っていることが望ましい. 注: 本記事は2021/03/02に全面的に書き直された. レビューありがとうございます: @kimiyuki_u CRT 準備 まず, 本節でしばしば利用される定理である以下について述べる. Thm. 0. 任意の非零自然数$a, b$に対し, 整数$x, y$が存在して, $ax + by = \gcd(a, b)$をみたす. この定理における$(x, y)$は存在性を示すのみならず$(a, b)$から具体的に計算することが可能であり, そ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
