Javaで暗号全部実装してみる?
おこめDES,AES,RSA,SHA-1,2,3くらいを実装した
AES実装で気になった点 long列で扱うとbyte列で扱うより速い
ビット演算まとめてできる機能がないのかも
おこめSHAKE128,SHAKE256は可変長出力で、SHA-3で出力できない? サイズのハッシュを自由に出力できる。
アルゴリズムはKeccakで同じ。長さのパラメータが必要で、内部的には初期化のビット列が少し違う。
RawSHAKE128,RawSHAKE256はKeccakの拡張用の元になる感じのものでSHA-3系と区別されるビット列が足されている。これにさらに足していくとSHAKE128,SHAKE256になる。
cSHAKE128/cSHAKE256 もKeccak 系のアルゴリズムを使用。
長い結果を出力するときはKeccakのスポンジ構造を利用することになる。
SHAKEもcSHAKEも元のデータには長さの情報がないので長さを変えても基本的な出力は変わらず後に出力が足されていく。これをXOFとしてハッシュとちょっと違う感じでまとめている。
SHAKE128,SHAKE256から拡張され、N のファンクション名とS のバリアントを指定することができる。この2つが入ることで同じデータでも目的が違えば別の値が出力される。NとSの両方が省略されるとSHAKE128,SHAKE256と同じ結果を出力する。NとSはビット列で指定可能。
おこめガロア体の実装
AES、GCMなどでガロア体や有限体が出てくるので作る
仕組みはいろいろ難しいがビット演算的なところ
0以外がぐるっと一周するような仕掛けになっている計算方法で、乱数っぽいので暗号によく使われる
AESでは8bit, GCMなどでは128bitが使われたりする。32bitなどもあり。
足し引きと掛け算を主に使えればよく、足し算引き算はXORで計算して桁上がりしないため結果は同じになる。掛け算はビットシフトの組み合わせで何とかなり、桁あふれの処理が特殊。
8bitでは素数的なものをa たとえば3、
aとbの組み合わせで処理できる場合は
割り算はできるかというと微妙に難しい。逆数を計算して掛け算に持っていくという方法で計算はできる。
GCMではビット列の順が逆になっているので気づかないといつまでも完成しない。
おこめ今では少し古くなったもののまだ使われていそうなRSA PRIVATE KEY の暗号解除法、AES対応の解説があんまり見かけないので詳細を調べてみた。
Proc-Type: 4,ENCRYPTED になっている形。3もなくはないが今はない。
基本的な形はPKCS #5 v1.5 の PBKDF1で繰り返しが1回。DESならこれでよかった。
DEK-Info に暗号モードと16進のIVが書かれている。
PKCS #5 のPBKDF1でハッシュ関数がMD5、saltとストレッチ回数1回、パスワード、出力サイズが必要。
PBES1ではアルゴリズム対応がちょっと足りない。
128bitのAESではDEK-Infoのsaltっぽいものも128bitになっているが、OpenSSLのPBKDF1の入力に使うのはIVの先頭64bitなので全部突っ込むと正しい結果が出てこなかった。
素のPBKDF1ではハッシュ長を超える出力ができない。OpenSSLではこれも拡張されている。
鍵導出関数 PBKDF1のOpenSSL風なのが次のような感じ。
int dkLen = keyバイト長
MD md = MD5
byte[] salt = IV の先頭64bit
byte[] dk = 出力先
do {
md.update(pass);
t = md.digest(salt); // salt はIVの先頭64bit
// c = 1 なのでループ省略
dk = dk + t; // という概念
md.update(t); // 次へ渡し
} while (dk.length < dkLen); // OpenSSLでは長さ制限なし
key = dkからdkLenを切り出し
AES-256-CBC なら128bit x 2 でループ2回
key と IV (128bit)をブロック暗号に渡して本文をどうこうすればそれっぽい結果が返ってくる。ブロック暗号系アルゴリズムの場合はPKCS7Paddingも必要。
おこめOpenBSD系かな BCrypt と Blowfish を実装。Blowfishはブロック暗号。BCryptはBlowfishを利用するパスワード暗号化。
Blowfishは448bitまでの鍵が利用可能とされているがBCryptなどでは72文字(576bit)まで利用している。
円周率を元にした内部状態PとS的な配列を鍵で攪拌して、そのPとSの表を使ってDSAと似た感じで左右入れ換える形で暗号化するような形式。
IETFのInternet DraftからBlowfishを実装してみたが、いろいろ間違っているようなので他の資料を探して直していく必要があった。テストベクターは正確。
BCryptはパスワード用に定番のカウントcostと乱数saltを持っている。が癖も多いかもしれない。Blowfishにsaltを含めた初期化の処理を追加する。最初からsalt込みでBlowfish作ってみてもいいか。
BCryptのsaltは128bit固定。パスワードを暗号化するのではなくBlowfishの鍵として利用する。
定型文を繰り返し暗号化する形なので出力からパスワード(Blowfishの鍵)を復号することはできない構造。
costは直接くり返す数ではなく、
BCryptで入力するパスワードは\0終端も含める形で利用する。
出力はhashといえばhashか? 入力サイズに制限があるのでchecksumぐらいなのか?
出力はshadowパスワードなどの共通形式Modular Crypt Formatで
おこめ証明書、よく見るが中身は知られていないような気がする
LDAPっぽい名前と公開鍵、機能をCAの名前をつけて署名したもの、でいいかな
X.509で定義されているらしいが、それをインターネット用Profileという形でまとめたものにRFC 5280がある
ASN.1もひととおり必要だが作っておくと大抵の型式にまるっと変換するのも楽になるかもしれないよ、という型式にしてみるとおすすめ。ASN.1のデータ型をJavaやJSONとSoftLibRebindを使ってすり合わせる。DERほぼ対応。JER, XERではないが似たようなもののできあがり。
SoftLibASN1とSoftLibRebindなどにまとめ。
名前のLDAP系がまだ足りない。
おこめEdDSAに手を出してみたところ数式的な謎が多くてとっかかりがわからない。
まずEdDSAではDSA系の署名ができる。暗号化はDiffie-Hellmanを楕円暗号にしたECDHのEdDSAっぽい派生版を使う。
とりあえず基本のDSAとDHの手順をおさえてみよう。
g^n mod p から nを計算するのは難しいよというところから暗号として成り立つ。
g^n になっている部分を [n]G っぽい楕円の計算に置き換える。nは足し算掛け算ができるので結果的に同じ理屈で暗号になるよという形。
楕円曲線は種類があり、ECDSAとEdDSAでは違うものを使っている。ECDHではどちらの系統のものもある。
ECDSAの曲線はいろいろあるが、EdDSAの曲線はとりあえず2つだけ。
ECDHではCurve25519とCurve449があり、EdDSAのEdWards25519とEdWards449の式を少し変更したものになっているので厳密に同じものではない。
識別名としてはEdDSAがEd25519とEd448，ECDHの方がX25519とX448という名前になっている。
EdDSAでは乱数生成にハッシュを利用する。秘密鍵からSHA512やSHAKE256で作ったものを半分にして少し整えたsを楕円曲線に掛け算すると公開鍵Aになる。A = [s]B
Bは楕円曲線の基準になる点、Aも点の座標
署名
EdDSAでは本文を加えたハッシュは2つ生成する
dom は署名の種類を判別するものだがPureEdDSA(Ed25519)ではとりあえず略。
メッセージMに秘密鍵のハッシュの半分などいろいろ加えたもののハッシュをr、楕円曲線掛け算したものはR = [r]B
検証に使える値(dom, R， A， 本文) を詰め込んで計算したハッシュをk
S = r + k * s
sはAの元 A = [s]B
RとSを繋げて署名として公開
検証
R と S 署名
A 公開鍵
dom Ed25519では空
k' = H(dom, R, A, 本文) のハッシュを計算 署名側のkと同じ
R + [k']A を計算
[S]B を計算
RとAは楕円曲線の座標なので楕円曲線上で足し算
R = [r]B, A = [s]B なので
R + [k']A = [r]B + [k][s]B = [r + k * s]B
S = r + k * s
ということで楕円曲線上の計算と楕円曲線を使わない計算の2つが同じになっている証明
秘密鍵、r、sは公開側には秘密
秘密鍵は長さ自由でも良さそう
rは適当に違う計算してもよさそう
という結論
楕円の中身がわからなくてもEdDSAの外側はこんな感じ