Crypto

特徴的な素因数分解アルゴリズムを実装してみる

「単純な素因数分解アルゴリズムを実装してみる」 ではPollard-Rhoアルゴリズムなど、「Msieveを使って大きな数を素因数分解してみる」 では複数多項式二次ふるい法(MPQS)などの素因数分解アルゴリズムの実装と評価を行った。 ここでは、上記以外の素因数…

LWE格子暗号による暗号化をやってみる

近年、量子コンピュータ研究の進展により、量子コンピュータでも解くのが難しい暗号(Post-quantum cryptography; 耐量子計算機暗号)への注目が高まっている。 ここでは、耐量子計算機暗号のひとつであるLWE格子暗号の原理を説明し、単純化したアルゴリズム…

Pari/GPで楕円曲線離散対数を計算してみる

「Pari/GPでECDH鍵交換、ECDSA署名をやってみる」では、数式処理システムPari/GPを使ってECDH鍵交換、ECDSA署名の計算を行った。 これらの楕円曲線暗号は、楕円曲線離散対数問題(ECDLP)と呼ばれる問題が計算量的に困難であることを安全性の根拠としている…

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の概要を説明し、これを題材…

plain RSAに対するLSB decryption oracle attackをやってみる

「RSAに対する適応的選択暗号文攻撃とパディング方式」では、パディングなしのRSA(plain RSA)が選択暗号文攻撃に対して安全でない、つまり任意の暗号文を復号した結果を得られるとき、与えられた暗号文を直接復号することなく平文が得られることについて確…

Pari/GPでECDH鍵交換、ECDSA署名をやってみる

TLS 1.2では、楕円曲線暗号であるECDH鍵交換、ECDSA署名を使うことができる。 ここでは、数式処理システムPari/GPを使ってこれらの計算をやってみる。 環境 Ubuntu 14.04.4 LTS 64bit版、Pari/GP 2.5.5 $ uname -a Linux vm-ubuntu64 3.19.0-25-generic #26~…

メッセージダイジェスト(MD)、メッセージ認証コード(MAC)、鍵導出関数(KDF)の違いについてのメモ

「ハッシュ」という言葉があいまいに使われている場面をしばしば目にするので、関係する概念とそれらの違いについてまとめてみる。 メッセージダイジェスト(Message Digest; MD) MD5、SHA-1、SHA-256など、あるバイト列(メッセージ)に対し固定長の要約値…

Mersenne Twisterの出力を推測してみる

「Z3Pyでglibc rand(3)の出力を推測してみる」および「Z3Pyでxorshift128+の出力を推測してみる」では、Z3Pyを使って疑似乱数生成アルゴリズムのいくつかの出力を観測することで、後続の出力を推測した。 ここでは、Pythonのrandomモジュールなどで利用され…

Z3Pyでxorshift128+の出力を推測してみる

「Z3Pyでglibc rand(3)の出力を推測してみる」では、glibc rand(3)の出力をいくつか観測することで、後続の出力を推測した。 ここでは、V8 JavaScript Engineなどで使われている疑似乱数生成アルゴリズムxorshift128+の出力を推測してみる。 環境 Ubuntu 14.…

Z3Pyでglibc rand(3)の出力を推測してみる

疑似乱数列は、いくつかの出力を観測することにより内部状態を復元することで推測が可能である。 ここでは、SMTソルバZ3Pyを使い、glibc rand(3)の出力を推測してみる。 環境 Ubuntu 14.04.3 LTS 64bit版、EGLIBC 2.19 $ uname -a Linux vm-ubuntu64 3.19.0-…

PythonでPEM形式のRSA鍵を生成する方法のメモ

適当なパラメータをもとに、PythonでPEM形式のRSA鍵を生成する方法のメモ。 環境 Ubuntu 14.04.3 LTS 64bit版 $ uname -a Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux $ lsb_…

RSAに対する適応的選択暗号文攻撃とパディング方式

「plain RSAに対する攻撃手法を実装してみる」では、平文をそのまま暗号化した場合のRSA(plain RSA)に対するいくつかの攻撃手法を実装した。 他にも、plain RSAについては適応的選択暗号文攻撃(CCA2)に対して安全でないことが知られている。 ここでは、p…

SageMathを使ってCoppersmith's Attackをやってみる

「plain RSAに対する攻撃手法を実装してみる」では、plain RSAに対する種々の攻撃手法を実装した。 plain RSAに対する攻撃手法には、他にもCoppersmithの定理に関連した手法が知られている。 ここでは、Pythonベースの数式処理システムSageMathを用いてこれ…

plain RSAに対する攻撃手法を実装してみる

RSAは「単純な素因数分解アルゴリズムを実装してみる」「Msieveを使って大きな数を素因数分解してみる」「YAFUを使って大きな数を素因数分解してみる」で示したような方法により、公開鍵nを素因数分解することができれば秘密鍵dを得ることができる。 一方、…

YAFUを使って大きな数を素因数分解してみる

「Msieveを使って大きな数を素因数分解してみる」では、Msieveを使って大きな数の素因数分解を行った。 素因数分解プログラムには、Msieveの他にYAFU(Yet Another Factorization Utility)がある。 YAFUはECMにGMP-ECM、MPQSにMsieve、GNFSにGGNFSを用い、…

Msieveを使って大きな数を素因数分解してみる

「単純な素因数分解アルゴリズムを実装してみる」では、実装の容易な素因数分解アルゴリズムをPythonで実装し、一般的なPCで解くことができるbit数などを調べた。 より大きな数を素因数分解できるアルゴリズムには、楕円曲線法(ECM)、複数多項式二次ふるい…

単純な素因数分解アルゴリズムを実装してみる

「OpenSSLとPythonでRSA暗号の原理を知る」で書いたように、RSA暗号は公開鍵である整数modulusを二つの素数に素因数分解することができれば破ることができる。 ここでは、いくつかの単純な素因数分解アルゴリズムをPythonで実装し、一般的なPCで解くことがで…

CBC modeに対するPadding oracle attackをやってみる

この記事は「脆弱性"&'<<>\ Advent Calendar 2015」23日目の記事です。 ブロック暗号モードのひとつであるCBC modeには、Padding oracle attackと呼ばれる攻撃手法が存在することが知られている。 これは、繰り返し復号を行うことができ、かつ復号の成否が観…

「CRYPT+YOU, UNDERSTAND TODAY!」というタイトルでプレゼンした

Security Casual Talks 2014#2 - すみだセキュリティ勉強会 代表的な暗号アルゴリズムとそれらに関連するトピックについて話した。 CRYPT+YOU, UNDERSTAND TODAY! from inaz2 タイトルの元ネタはもちろんJava。勉強会自体が今回はわりと盛況だった。 次はあ…

Pythonでストリーム暗号RC4を実装し、脆弱性の一端を垣間見る

この頃、SSLの暗号化などにストリーム暗号RC4を使わないほうがいいといった話がよく聞かれるようになった。 2013年版のCRYPTREC暗号リストでも128bitのRC4が「運用監視暗号リスト」に入っているし、先日には、Microsoftからストリーム暗号RC4を使わないよう…

OpenSSLとPythonでRSA暗号の原理を知る

OpenSSLを使うと、次のようにして2048bitのRSA鍵が作成できる。 $ openssl genrsa 2048 Generating RSA private key, 2048 bit long modulus ......................+++ .................+++ e is 65537 (0x10001) -----BEGIN RSA PRIVATE KEY----- MIIEowI…