読者です 読者をやめる 読者になる 読者になる

古典暗号 - 一致指数を用いた多表式暗号の解読

この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です. 多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが…

ECDLPに対する攻撃手法のまとめ - 一般的攻撃手法

Exhaustive Search法 いわゆる全探索法であり, 力任せな方法. 与えられる楕円曲線$E$とその上の点$P$, $Q$について$m = \#P$とする. この時, ECDLPの解$d$は$1 \leq d \leq m $の不等式を満たす. このため, この$d$の範囲を全て計算してみることでECDLPは解…

ECDLPに対する攻撃手法のまとめ 概要編

楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, 以下ECDLP)が解けるか否か, という問題は暗号理論において楕円曲線が用いられる際の安全性基準として一般的である. 本記事から數回に分けてECDLPに対する攻撃手法についてまとめる. ECDLP…

射影座標を用いた場合のMiller Algorithmについてのメモ

Miller Algorithmの実装を高速化した際のメモ。 Miller Algorithmは基本紹介される際にはEuclid空間上の楕円曲線の点について紹介されるが、変数変換をしてやることで射影座標上のアルゴリズムとすることが出来る。(なお、Miller Algorithm自体は任意の種数…

楕円曲線の位数2, 3を持つ点の個数

$\def\O{\mathcal{O}}$ ここでは標数2, 3の体は考えないため, 全ての楕円曲線はWeierstrass標準形 $y ^ 2 = x ^ 3+ax+b$ で表せるとする. また, 楕円曲線上の点 $P$ の $x$ 座標を $x(P)$ , $y$ 座標を $y(P)$ と表す. 位数2の点 複素数体上の楕円曲線 $y ^ …

数学 - 中国人剰余定理

中国人剰余定理とは、初等整数論の定理の一つであり、非常に多くの応用が存在する定理である。この記事では、この定理に注目してその一般化と応用について解説する。 連立合同方程式 補題 連立合同方程式 $$ \begin{align} x &\equiv a \mod n_1\\ x &\equiv…

公開鍵暗号 - RSA - Wiener's Attack

この記事では、RSA暗号への攻撃の中で恐らく最も有名であろうWiener's Attackについて取り上げる。多くは原論文を参考にしているが、証明の省略やアルゴリズムの一部改変等があるので、この記事を読んで氣になったのであればぜひとも原論文を読んで実際に実…

公開鍵暗号 - Paillier暗号

この記事では比較的新しい、かつ珍しい加法準同型性を持つPaillier暗号について解説する。 Paillier暗号とは、Pascal Paillierによって1999年に発明された公開鍵暗号で、素因数分解を安全性の根拠としている。この暗号は、メッセージ\(Enc(m_1), Enc(m_2)\)…

公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解

RSAにはいくつもの攻撃手法が存在する。その中から、Common Modulus Attackと秘密鍵dからnを素因数分解することを取り上げる。 Common Modulus Attack RSAの教科書にも載るようなわかりやすく、簡単な攻撃で、次のように定義される。 RSA公開鍵\((n, e_1)\),…

古典暗号 - Beaufort暗号とAutokey暗号

Vigenere暗号は非常に強力な暗号だった。その強力さと汎用さから、いくつかの派生暗号が知られている。ここでは、その中から2つ取り出して書いてみようと思う。 Autokey暗号 Autokey暗号は、Vigenere暗号にストリーム暗号の要素を加えた暗号と言える。以下に…

公開鍵暗号 - RSA - 基礎

この記事では、公開鍵暗号の先駆けとして非常に有名なRSA暗号とその原理、幾つかの攻撃手法についての解説を書く。個々の攻撃手法については後々書いていく予定だ。 公開鍵暗号 公開鍵暗号について一通りの説明をする。我々が普段暗号と呼ぶものは、基本的に…

古典暗号 - Vigenere暗号とカシスキー・テスト

この記事は古典暗号の中でも複雑で解読しにくいとされている多表式換字式暗号であるVigenere暗号と、多くの場合に効果的な解読法であるカシスキー・テストを理解することを目標に書く。 Vigenere暗号 Vigenere暗号は頻度分析が発達し単一換字式暗号がある程…

古典暗号 - アフィン暗号

古典暗号のうち、シーザー暗号を始めとする多くの単一換字式暗号を一般化すると、アフィン暗号と呼ばれる暗号に帰着することができる。今回はアフィン暗号とその応用例、解読法について書く。 アフィン暗号 アフィン暗号の暗号化関数は、次の式で定義される…