現代暗号入門 いかにして秘密は守られるのか
神永正博著「現代暗号入門 いかにして秘密は守られるのか」講談社 (2017/10/18)
https://www.amazon.co.jp/dp/product/4065020352/
シーザー暗号、バーナム暗号、LFSR、RC4(KSA, PRGA)、DES、AES、ICカード、ハッシュ関数(MD5)、公開鍵暗号（RSA）、楕円曲線暗号、ガロア体、離散対数、ECDSA、ビットコイン、計算量、一方向性関数、フォールトアタック（差分故障解析）、差分電力解析（DPA）などについて概説。
（正誤表）
http://bluebacks.kodansha.co.jp/books/9784065020357/appendix/attachments/errata.pdf
以下、読後メモ。
Pythonでストリーム暗号RC4を実装し、脆弱性の一端を垣間見る
http://inaz2.hatenablog.com/entry/2013/11/30/233649
https://qiita.com/tnakagawa/items/54f360f144a2ba2fe0a0
\[a^{(p-1)(q-1)}≡1 (mod ~N)\]
の両辺を\(k\)乗すると、
\[\bigl\{a^{(p-1)(q-1)}\bigr\}^k≡1^k (mod ~N)\]
\[a^{(p-1)(q-1)k}≡1 (mod ~N)\]
\[a×a^{(p-1)(q-1)k}≡a×1 (mod ~N)\]
\[a^{k(p-1)(q-1)+1}≡a (mod ~N)\]
ここで、\(a\)を\(M\)と置き換え、\(k(p-1)(q-1)+1\)を \(ed\) と置き換えると、
\[M^{ed}≡M (mod ~N)\]
となり、p105 の７行目の式が導かれる。
において、\(M^e\) を\(C\) と置くと、
\[M^{ed}≡C^d≡M (mod ~N)\]
左項と中項の合同にのみ着目すると、
\[C^d≡M^{ed} (mod ~N)\]
これの累乗根 \(d√ \)をとると、
\[C≡M^e (mod ~N)\]
となり、p105 の４行目の式が導かれる。
とあるのは、
\[C mod 187=19^3 mod~187\]
が正しい。すなわち、
\(C\)を\(N\)で割った余りが、\(M^e\) を\(N\)で割った余りに等しいことを示す式たる
\[C mod~N=M^e mod~N\]
合同式では、
\[C≡M^e (mod ~N)\]
において、
平文\(M\) に19、
公開指数\(e\) に3、
公開モジュラス\(N\)に187 を代入すると、
\[C≡19^3 (mod ~187)\]
通常式では、
\begin{eqnarray}
C mod ~187 &=& 19^3 mod ~187 \nonumber \\
&=& 6859 \nonumber \\
&=& 127 \nonumber
\end{eqnarray}
\[C=127, 127+187, 127+187×2, …\]
となるので、
その最小値127 を暗号文とする。
\[C^d≡M (mod ~N)\]
の両辺を入れ替えて、
\[M≡C^d (mod ~N)\]
暗号文\(C\)に127、
秘密指数\(d\) に107、
公開モジュラス\(N\)に187 を代入すると、
\[M≡127^{107} (mod ~187)\]
通常式では、
\begin{eqnarray}
M mod ~187 &=& 127^{107} mod ~187 \nonumber \\
&=& 19 \nonumber
\end{eqnarray}
\[M=19, 19+187, 19+187×2, …\]
となるので、
その最小値19 をとると、
平文 \(M=19\) と復号される。
https://qiita.com/srtk86/items/aaaf7225d9861512a63d
\begin{eqnarray}
\bigl\{(C_1)^2×(C_2)^{-1}\bigr\} mod ~N &=& ((M^3)^2×(M^5)^{-1})mod ~N \nonumber \\
&=& M mod ~N \nonumber
\end{eqnarray}が成立する。
ここで、平文\(M＜公開モジュラスN\) であるから、\[M mod ~N=M\]を上式に代入すると、平文\(M\) を求める式は、\[M=\bigl\{(C_1)^2×(C_2)^{-1}\bigr\} mod ~N\]
なお、\(6303^{-1} mod ~540031=55948\) となる理由？
https://www.amazon.co.jp/dp/product/4065020352/
シーザー暗号、バーナム暗号、LFSR、RC4(KSA, PRGA)、DES、AES、ICカード、ハッシュ関数(MD5)、公開鍵暗号（RSA）、楕円曲線暗号、ガロア体、離散対数、ECDSA、ビットコイン、計算量、一方向性関数、フォールトアタック（差分故障解析）、差分電力解析（DPA）などについて概説。
（正誤表）
http://bluebacks.kodansha.co.jp/books/9784065020357/appendix/attachments/errata.pdf
以下、読後メモ。
第１章 共通鍵暗号
p16 Python でシーザ暗号を実装する
https://qiita.com/l7u7ch/items/7ee122cfa3dc89919327p30 Linear Feedback Shift Register
https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF?fbclid=IwAR1ZeZzsnTmyBc2E9mOfiGoGEDuFkPd1Xdh4BL53HjH2R-qU89Q57Ie65zYp33 key-scheduling algorithm (KSA) のコード例
Pythonでストリーム暗号RC4を実装し、脆弱性の一端を垣間見る
http://inaz2.hatenablog.com/entry/2013/11/30/233649
p44、45 共に下3行目
「秘密鍵」とあるのは、「ラウンド鍵」の趣旨か。第２章 ハッシュ関数
p79 MD5によるハッシュ値
import hashlib dat = 'Information is not knowledge.' # MD5のハッシュ値 hashlib.md5(dat.encode()).hexdigest()
66ccbf379cd611b78bef50557efa29a3
p80 ピリオドが無い文のハッシュ値
# コードは上記の続き dat2 = 'Information is not knowledge' hashlib.md5(dat2.encode()).hexdigest()
3c70d9e8d84525ca930032663c7e1f74
第３章 公開鍵暗号（RSA暗号）
p103 オイラーの定理（素数）
オイラーの\(φ\)関数について、\(φ(pq)＝φ(p)φ(q)\) の証明https://qiita.com/tnakagawa/items/54f360f144a2ba2fe0a0
p104 合同式
合同式（合同記号 ≡ の左右の整数の値を括弧内の \(mod\) で示した値で各々割った余りが等しい）において、\[a^{(p-1)(q-1)}≡1 (mod ~N)\]
の両辺を\(k\)乗すると、
\[\bigl\{a^{(p-1)(q-1)}\bigr\}^k≡1^k (mod ~N)\]
\[a^{(p-1)(q-1)k}≡1 (mod ~N)\]
\[a×a^{(p-1)(q-1)k}≡a×1 (mod ~N)\]
\[a^{k(p-1)(q-1)+1}≡a (mod ~N)\]
ここで、\(a\)を\(M\)と置き換え、\(k(p-1)(q-1)+1\)を \(ed\) と置き換えると、
\[M^{ed}≡M (mod ~N)\]
となり、p105 の７行目の式が導かれる。
p105 メッセージM
\[M^{ed}≡M (mod ~N)\]の両辺を入れ替えて、\[M≡M^{ed}~ (mod ~N)\]において、\(M^e\) を\(C\) と置くと、
\[M^{ed}≡C^d≡M (mod ~N)\]
左項と中項の合同にのみ着目すると、
\[C^d≡M^{ed} (mod ~N)\]
これの累乗根 \(d√ \)をとると、
\[C≡M^e (mod ~N)\]
となり、p105 の４行目の式が導かれる。
p106 Ｃ
\[C=19^3 mod~187\]とあるのは、
\[C mod 187=19^3 mod~187\]
が正しい。すなわち、
\(C\)を\(N\)で割った余りが、\(M^e\) を\(N\)で割った余りに等しいことを示す式たる
\[C mod~N=M^e mod~N\]
合同式では、
\[C≡M^e (mod ~N)\]
において、
平文\(M\) に19、
公開指数\(e\) に3、
公開モジュラス\(N\)に187 を代入すると、
\[C≡19^3 (mod ~187)\]
通常式では、
\begin{eqnarray}
C mod ~187 &=& 19^3 mod ~187 \nonumber \\
&=& 6859 \nonumber \\
&=& 127 \nonumber
\end{eqnarray}
\[C=127, 127+187, 127+187×2, …\]
となるので、
その最小値127 を暗号文とする。
p106 復号
合同式(p105)\[C^d≡M (mod ~N)\]
の両辺を入れ替えて、
\[M≡C^d (mod ~N)\]
暗号文\(C\)に127、
秘密指数\(d\) に107、
公開モジュラス\(N\)に187 を代入すると、
\[M≡127^{107} (mod ~187)\]
通常式では、
\begin{eqnarray}
M mod ~187 &=& 127^{107} mod ~187 \nonumber \\
&=& 19 \nonumber
\end{eqnarray}
\[M=19, 19+187, 19+187×2, …\]
となるので、
その最小値19 をとると、
平文 \(M=19\) と復号される。
p108 素数が無数に存在することの証明
https://mathtrain.jp/prime （高校数学の美しい物語）p110 素数定理
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%AE%9A%E7%90%86?fbclid=IwAR3pqLE4c-WqX2KFkunxQu5rwuzumfmAVria3OE20IbpUDZ_co6wyyIIeQUp111 フェルマーテスト・ミラーラビン素数判定法
https://qiita.com/srtk86/items/609737d50c9ef5f5dc59p111 AKS素数判定法
https://qiita.com/srtk86/items/aaaf7225d9861512a63d
p142 復元可能なメッセージ
\[\left\{\begin{array}{l}C_1≡M^3 (mod ~N)\\C_2≡M^5 (mod ~N)\end{array}\right.\] から、\[\left\{\begin{array}{l}(C_1)^2≡(M^3)^2 (mod ~N)\\(C_2)^{-1}≡(M^5)^{-1} (mod ~N)\end{array}\right.\] なので、両辺を掛け合わせて、\[(C_1)^2×(C_2)^{-1}≡(M^3)^2×(M^5)^{-1} (mod ~N)\]通常式では、\begin{eqnarray}
\bigl\{(C_1)^2×(C_2)^{-1}\bigr\} mod ~N &=& ((M^3)^2×(M^5)^{-1})mod ~N \nonumber \\
&=& M mod ~N \nonumber
\end{eqnarray}が成立する。
ここで、平文\(M＜公開モジュラスN\) であるから、\[M mod ~N=M\]を上式に代入すると、平文\(M\) を求める式は、\[M=\bigl\{(C_1)^2×(C_2)^{-1}\bigr\} mod ~N\]
なお、\(6303^{-1} mod ~540031=55948\) となる理由？
p145 中国の剰余定理
https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86?fbclid=IwAR0XZuOYdcMRftaOLPDvKmLoT0Tp63ZB6HrMw_NfDmFI4NupGLGHT62oQxc第４章 公開鍵暗号（楕円曲線暗号）
p156 図78 楕円曲線
\(y^2=x^3+x+1\) のグラフ
p163 有限体
有限体\(F(p)\) 上の楕円曲線
http://mattyuu.hatenadiary.com/entry/2017/01/29/161758 （mattyuuの数学ネタ集）
http://mattyuu.hatenadiary.com/entry/2017/01/29/161758 （mattyuuの数学ネタ集）
p163 図84
\(GF(79)\)における曲線 \(y^2=x^3+x+1\) のExcelプロット
p164 スカラー倍算
有限体上の楕円曲線 \(y^2=x^3+ax+b\) 上のスカラー倍算
https://tex2e.github.io/blog/crypto/elliptic-curve-scala-mul
\[(x_3,y_3)=(x_1,y_1)+(x_2,y_2)\]
の加算演算
\[x_3=λ^2-x_1-x_2~~~mod~p\]
\[y_3=λ(x_1-x_3)-y_1~~~mod~p\]
\[λ=\frac{y_2-y_1}{x_2-x_1}~~~mod~p~~~if~P≠Q\]
\[λ=\frac{3x_1^2+a}{2y_1}~~~mod~p~~~if~P=Q\]
のとき、\(2P(x_2,y_2)\) は、加算演算で、\(P=Q\)
\[(x_2,y_2)=(x_1,y_1)+(x_1,y_1)\]
の場合なので
\[x_2=λ^2-x_1-x_1~~~mod~p\]
\[y_2=λ(x_1-x_2)-y_1~~~mod~p\]
\[λ=\frac{3x_1^2+a}{2y_1}~~~mod~p~~~if~P=Q\]
により計算する。先ず、末式分母は、\(2y_1\)の逆数を指すから、これを求める。
\[2×y_1=26\]
の\(GF(79)\)上の逆数は、下記の乗算Excel表を参照すると、76である。
よって、この結果及び楕円曲線の係数\(a=1\)を代入して、
\begin{eqnarray}
λ&=&(3×x_1^2+1)×76 ~ mod~79 \nonumber \\
&=& 988~ mod~79 \nonumber \\
&=& 40 \nonumber \\
&& \nonumber \\
x_2&=&(λ^2 -2×x_1) ~ mod~79 \nonumber \\
&=&(40^2 -2×2) ~ mod~79 \nonumber \\
&=&1596 ~ mod~79 \nonumber\\
&=&16 \nonumber \\
&& \nonumber \\
y_2&=&\bigl\{λ(x_1-x_2) -y_1\bigr\}~mod~79 \nonumber \\
&=&\bigl\{40(2-16) -13\bigr\}~mod~79 \nonumber\\
&=&-573~mod~79 \nonumber\\
&=&59 \nonumber
\end{eqnarray}
よって、\(2P=(16,59)\) となる。
なお、負の数の割り算と余りについて、
http://naop.jp/topics/topics46.html （高校数学なんちな）
https://tex2e.github.io/blog/crypto/elliptic-curve-scala-mul
\[(x_3,y_3)=(x_1,y_1)+(x_2,y_2)\]
の加算演算
\[x_3=λ^2-x_1-x_2~~~mod~p\]
\[y_3=λ(x_1-x_3)-y_1~~~mod~p\]
\[λ=\frac{y_2-y_1}{x_2-x_1}~~~mod~p~~~if~P≠Q\]
\[λ=\frac{3x_1^2+a}{2y_1}~~~mod~p~~~if~P=Q\]
p164 計算過程
\[P(x_1,y_1)= P(2,13)\]のとき、\(2P(x_2,y_2)\) は、加算演算で、\(P=Q\)
\[(x_2,y_2)=(x_1,y_1)+(x_1,y_1)\]
の場合なので
\[x_2=λ^2-x_1-x_1~~~mod~p\]
\[y_2=λ(x_1-x_2)-y_1~~~mod~p\]
\[λ=\frac{3x_1^2+a}{2y_1}~~~mod~p~~~if~P=Q\]
により計算する。先ず、末式分母は、\(2y_1\)の逆数を指すから、これを求める。
\[2×y_1=26\]
の\(GF(79)\)上の逆数は、下記の乗算Excel表を参照すると、76である。
よって、この結果及び楕円曲線の係数\(a=1\)を代入して、
\begin{eqnarray}
λ&=&(3×x_1^2+1)×76 ~ mod~79 \nonumber \\
&=& 988~ mod~79 \nonumber \\
&=& 40 \nonumber \\
&& \nonumber \\
x_2&=&(λ^2 -2×x_1) ~ mod~79 \nonumber \\
&=&(40^2 -2×2) ~ mod~79 \nonumber \\
&=&1596 ~ mod~79 \nonumber\\
&=&16 \nonumber \\
&& \nonumber \\
y_2&=&\bigl\{λ(x_1-x_2) -y_1\bigr\}~mod~79 \nonumber \\
&=&\bigl\{40(2-16) -13\bigr\}~mod~79 \nonumber\\
&=&-573~mod~79 \nonumber\\
&=&59 \nonumber
\end{eqnarray}
よって、\(2P=(16,59)\) となる。
なお、負の数の割り算と余りについて、
http://naop.jp/topics/topics46.html （高校数学なんちな）
第５章 サイドチャネルアタック
p199 Aの電子署名依存性
\(A=f(S_p)\)