CS专业课学习笔记
情報セキュリティ(information security)とは、様々なセキュリティ上の危険や脅威 から情報資産 を保護し、機密性 (Confidentiality)、完全性 (Integrity)、可用性 (Availability)の3つの観点で正常な機能・状態を保持することにより、情報ステムや情報の信頼性を高め、情報システムの利用者が安心して情報システムを利用できるようにすることである
情報セキュリティ(CIA)
定義
機密性
その情報にアクセスを許可されたものだけがアクセスできるようにすること
完全性
情報およびその処理方法が正確であり完全であるようにすること
可用性
正当な利用者が必要な時に情報および関連する資産に確実にアクセスできる状態を保つこと
本人認証
情報の作成者や送信者が本物であることを保証すること
責任・監査
システムが、いつ、誰に利用されたかを追跡できること
プライバシ
情報やサービスの利用が他人に観察されないようにすること
組織が情報資産を活用するにあたり、情報セキュリティ上保護すべき対象範囲と、 それらの対策や管理運用方針などを文書化したもの
組織のセキュリティ方針の根幹をなすもの
組織のトップ（上層部・経営層）によって承認され、情報資産にかかわるすべての人員に周知徹底（ISMS（Infromation Security Management System)認証基準）
目的
用語の定義
適用範囲
基本原則及び方針
組織体制及び責任と権限
諸規定との関連
教育・訓練
監査
評価と見直し
セキュリティ事故への対応
例外処理
罰則規定
セキュリティ基本方針
情報セキュリティのための組織
資産分類
人的資源のセキュリティ
物理的および環境的セキュリティ
通信および運用管理
アクセス制御
情報システムの取得、開発およびメンテナンス
情報セキュリティインシデント
事業継続管理
適合性
物理的資産
情報・データ
ソフトウェア
製品やサービス 企業イメージ
人員
セキュリティリスクの評価式：リスク ＝ 資産価値 × 脅威 × 脆弱性
ベースラインアプローチ：
定性分析手法で、組織全体を俯瞰し、既存の標準や規定を基に一定のセキュリティレベルに準拠しているかを調査する手法
非形式アプローチ：
今までの経験に基づいた定性的なリスク分析手法コンサルタントのレベルにより分析結果が左右される
詳細アプローチ：
定量的分析手法で、組織全体のすべての情報資産を洗い出し、各脅威の発生確率と脆弱性の重要度に関する評価を行い、それを基にリスクの大きさを評価する手法
組み合わせアプローチ：
システムの構成や業務に応じて、ベースラインアプローチと詳細アプローチを使い分ける
不正攻撃（ポートスキャン、Dos(Denial of Sevices） DDos
侵入 (トロイの木馬、バッファーオーバーフロー、バックドア）
マルウェア（ウイルス、ワーム、スパイウェア、ランサムウェア）
盗聴
改ざん
なりすまし
持ち出し
ソーシャルエンジニアリング
事故・災害
紛失
不作為の作為
(1)~(3)：ソフトウェアを含めてコンピューターに関わるもの
ポートスキャン(Port scanner) ： 攻撃の糸口を発見するための手段Dos(Denial of Sevrices) ：大量のデータを送りつけることで負荷をかけシステムをダウンさせるDDoS(Distributed Denail of Services) ：複数個所に分散したDoS攻撃（１か所からアクセスが集中するDoS攻撃は検知がしやすいため、複数個所から攻撃することで、検出されにくくしている）
トロイの木馬(Trojan Horse) ：不正ファイルを実行させることで、 悪意のある機能を実行させるバッファーオーバーフロー(Buffer overflow) ：セキュリティホールの１つバッファに想定以上の長さのデータが入力されてしまうバグ（（スタック） あふれた値で関数の戻り先アドレスを上書きすることにより、制御を奪うことができる）バックドア(Backdoor) ：不正者が使用権を確認するコンピュータの機能を無許可で利用するために、コンピュータ内に設けられた通信接続の機能侵入後仕掛けることで、次回以降の侵入をより容易にする
malware = 「malicious」＋「software」
ウイルス : 他のプログラムやファイルの一部を書き換え、自己複製する機能をもつマルウェアワーム(worm) : 自身を複製して他のシステムに拡散する(Code Red, Nimda, Sobig, Mydoom, Conficker)スパイウェア(spyware) : コンピュータの内部情報を外部に送信（情報収集）(キーロガー、アドウェア、ダウンローダ)ランサムウェア(ransomware) : コンピュータをロックしたり、重要なファイルを暗号化して読めなくし、身代金(ransom)を要求する(AIDS Trojan, PC Cyborg, Reveton, CryptoLocker)
マルウェアの感染経路:
Web閲覧：メールに添付されたURLに誘導
Web誘導：偽セキュリティソフト配布サイト誘導感染
ネットワーク：セキュリティホール（無線パスワード未使用等）
メール添付：添付ファイル内（偽装）
外部記憶媒体：USBメモリ、ディジタルカメラ
ファイル共有ソフト
マクロプログラム：Office(VBA)
不正攻撃・マルウェア対策：
ファイアーウォール ： パケットフィルタリングアクセスログ ： 定期的な監視不要なポートを無効にする バージョン管理、セキュリティパッチ アンチウイルスソフトウェアの導入
SQLインジェクション(SQL injection) ：Webアプリケーションの入力データとしてSQL文を入力し、想定外のSQL文を意図的に実行させることでデータベースを攻撃する手法クロスサイトスクリプティング(Cross-site scripting，简称XSS) ：Webページを動的に生成するアプリケーションのセキュリティ上の不備を意図的に利用し、サイト間を横断して悪意のあるスクリプトを混入させることでユーザのCookie(ユーザ情報、セッション情報)を盗む などの攻撃手法クロスサイトリクエストフォージェリ(Cross-site request forgery，通常缩写为CSRF或XSRF) ：悪意のあるスクリプト が埋め込まれたWebページを訪問者に閲覧させて、別のWebサイトでその訪問者が意図しない操作を行わせる攻撃手法セッションハイジャック(Session hijacking) ：認証が完了してセッションを開始しているブラウザとWebサーバの間の通信において、CookieやセッションIDなどのセッション情報を盗むことで、対象セッションを通信当事者以外が乗っ取る攻撃手法
跟跨网站脚本（XSS）相比，XSS 利用的是用户对指定网站的信任，CSRF 利用的是网站对用户网页浏览器的信任
なりすまし(masquerading) ：攻撃者は通信をしている人のふりをして通信を行う（認証（IDの正当性）の侵害）中間者攻撃(man-in-the-middle attack) ：セッションの乗っ取りが先に行われ、アクティブな通信セッションが盗聴盗聴 ：ネットワーク等を流れる情報をアクセス権のない第三者が盗み見ること
受動的に行われる（ログが残らない）
ネットワーク上のどこで行われるかわからない
盗聴の主な手段:
コンピュータに直接仕掛ける
ネットワーク上のデータを読み取る
空気中のデータを読み取る（電磁界の変化を読み取る）：EMC等
持ち出し ：USBメモリなどの記録媒体に機密情報を保存し持ち出すソーシャルエンジニアリング(Social engineering) ：人間の心理的な隙や、行動のミスにつけ込んで個人が持つ秘密情報を入手する方法
重役や上司、重要顧客、システム管理者などと身分を詐称して電話をかけ、パスワードや重要情報を聞き出す
IDやパスワードが書かれた紙（付箋紙など）を瞬間的に見て暗記してメモする
学校の同級生の親族や警察・公安委員会・裁判所を名乗り、住所や電話番号などの個人情報を聞き出す
フィッシング(Phishing) ：インターネット上のユーザから経済的価値がある情報（ユーザ名、パスワード、クレジットカード情報）を奪う詐欺行為信頼されている主体になりすましたEメールによって偽のWebサーバに誘導することによって行われることが多い
攻撃者によってセキュリティ上の脅威の原因となる管理や設備の問題、システム上の誤りや設計の問題、またシステムの各種設定の問題など
脆弱性を最小化するには:
組織に関わる対策 ：セキュリティポリシ、情報セキュリティの運営組織ソフトウェアおよびハードウェアについての対策 ：ファイアウォール、侵入検知システム（ＩＤＳ）、アンチウイルスソフト、セキュリティパッチ、パスワード物理的対策 ：IDカード、施錠、バックアップ人的対策 ：責任範囲の明確化、パスワード管理、教育
技術：暗号技術をはじめ、バイオ情報による個人識別技術、電子透かし等による著作権保護、ウイルス対策、ファイアウォール、不正 侵入検知システム
管理・運営：ISO/IEC 15408，ISO/IEC17799
法制度：不正アクセス行為の禁止などに関する法律、知的財産権、個人情報保護法等
倫理
情報技術などの新しい技術の出現により、従来の法制度を適用できない事例 ⇒ \Rightarrow ⇒
不正アクセス行為の禁止などに関する法律
電気通信事業法
知的財産権
著作権法
個人情報保護法
IT基本法
ディジタルフォレンジックス(Digital forensics) ：不正アクセスや情報漏えいなどのセキュリティインシデントの発生時に、原因究明や法的証拠 を保全するために対象となる電子的記録 を収集・解析すること
古典暗号
換字式暗号
転置式暗号
シーザー暗号
スキュタレー暗号
現代暗号
共通鍵暗号 ：ブロック暗号，ストリーム暗号，DES，AES，バーナム暗号公開鍵暗号 ：RSA暗号，楕円曲線暗号，エルガマル暗号
量子暗号
盗聴の恐れのある通信路を通して安全に通信を行うために情報記号列を変換（暗号化 ）する技術
安全な記号列から元の情報記号列へ戻す（復号 ）には鍵 が必要
鍵による分類
共通鍵暗号 （秘密鍵暗号、対称暗号）：暗号化する鍵と復号する鍵が同一公開鍵暗号 （非対称暗号）：暗号化する鍵と復号する鍵が異なる
処理単位による分類
ブロック暗号 ：一定の長さの単位で処理ストリーム暗号 ：1bitごと処理
暗号系C: (P, C, K, E, D) 5つの集合により定義
P: 発生しうる平文 (plain text)の有限集合
C: 発生しうる暗号文 (cipher etxt)の有限集合
K: 可能性のある鍵 (key)の有限集合
E, D: 以下の性質を満たす関数の有限集合
e k E ∈ E , d k D ∈ D , k E ∈ K , k D ∈ K , x ∈ P , c ∈ C e_{k_E} \in E, d_{k_D} \in D, k_E \in K, k_D \in K, x \in P, c \in C e k E ∈ E , d k D ∈ D , k E ∈ K , k D ∈ K , x ∈ P , c ∈ C e k E : P → C , d k D : C → P e_{k_E}:P \rightarrow C, \quad d_{k_D}:C \rightarrow P e k E : P → C , d k D : C → P e k E ( x ) = c , d k D ( c ) = x , s . t . d k D ( e k E ( x ) ) = x e_{k_E}(x) = c, \quad d_{k_D}(c) = x, \quad s.t. \quad d_{k_D}(e_{k_E}(x)) = x e k E ( x ) = c , d k D ( c ) = x , s . t . d k D ( e k E ( x ) ) = x
安全性
暗号文c = e k D ( x ) ∈ C , x ∈ P , k D ∈ K c = e_{k_D}(x) \in C, x \in P, k_D \in K c = e k D ( x ) ∈ C , x ∈ P , k D ∈ K k ∈ K k \in K k ∈ K x ∈ P x \in P x ∈ P
鍵空間K K K ∣ K ∣ |K| ∣ K ∣
効率性
暗号化・復号の関数e k E ( ) ∈ E , d k D ( ) ∈ D , k E , k D ∈ K e_{k_E}() \in E, d_{k_D}() \in D, k_E, k_D \in K e k E ( ) ∈ E , d k D ( ) ∈ D , k E , k D ∈ K
現代暗号（共通鍵暗号）の基礎となる暗号方式、それぞれ単体では実用的ではない
換字暗号 (Substitution Cipher):平文の文字を別の文字で置き換える
転置暗号 (Permutation Cipher):平文の文字列を並び替える
P = C = Z n = { 0 , 1 , ⋯ , n − 1 } P = C = Z_n = \lbrace 0, 1, \cdots, n-1 \rbrace
P = C = Z n = { 0 , 1 , ⋯ , n − 1 }
K = { π = 0 1 ⋯ n − 2 n − 1 π ( 0 ) π ( 1 ) ⋯ π ( n − 2 ) π ( n − 1 ) : 置換 } \begin{aligned}
K = \begin{Bmatrix}
\pi = \begin{matrix}
0 & 1 & \cdots & n-2 & n-1
\\
\pi(0) & \pi(1) & \cdots & \pi(n-2) & \pi(n-1)
\end{matrix} : \text{置換}
\end{Bmatrix}
\end{aligned}
K = { π = 0 π ( 0 ) 1 π ( 1 ) ⋯ ⋯ n − 2 π ( n − 2 ) n − 1 π ( n − 1 ) : 置換 }
π ( 0 ) , ⋯ , π ( n − 1 ) \pi(0), \cdots, \pi(n-1) π ( 0 ) , ⋯ , π ( n − 1 ) Z n Z_n Z n 鍵空間の大きさ:∣ K ∣ = n ! = 1 ⋅ 2 ⋅ ⋯ ⋅ ( n − 1 ) ⋅ n |K| = n! = 1 \cdot 2 \cdot \cdots \cdot (n-1) \cdot n ∣ K ∣ = n ! = 1 ⋅ 2 ⋅ ⋯ ⋅ ( n − 1 ) ⋅ n
π ∈ K \pi \in K π ∈ K e π ( x ) : = π ( x ) e_{\pi}(x) := \pi(x) e π ( x ) : = π ( x ) d π ( y ) : = π − 1 ( y ) , π − 1 d_{\pi}(y) := \pi^{-1}(y), \quad \pi^{-1} d π ( y ) : = π − 1 ( y ) , π − 1 π \pi π
5 − 1 m o d 26 = 5 ⋅ x ( m o d 26 ) ≡ 1 ⇒ x = 21 5^{-1} \bmod 26 = 5 \cdot x \pmod {26} \equiv 1 \Rightarrow x = 21
5 − 1 m o d 2 6 = 5 ⋅ x ( m o d 2 6 ) ≡ 1 ⇒ x = 2 1
P = C = ( Z n ) m P = C = (Z_n)^m
P = C = ( Z n ) m
長さm m m Z n Z_n Z n
K = { π = 1 2 ⋯ m − 1 m π ( 1 ) π ( 2 ) ⋯ π ( m − 1 ) π ( m ) : 置換 } \begin{aligned}
K = \begin{Bmatrix}
\pi = \begin{matrix}
1 & 2 & \cdots & m-1 & m
\\
\pi(1) & \pi(2) & \cdots & \pi(m-1) & \pi(m)
\end{matrix} : \text{置換}
\end{Bmatrix}
\end{aligned}
K = { π = 1 π ( 1 ) 2 π ( 2 ) ⋯ ⋯ m − 1 π ( m − 1 ) m π ( m ) : 置換 }
π ( 1 ) , ⋯ , π ( m ) \pi(1), \cdots, \pi(m) π ( 1 ) , ⋯ , π ( m ) Z m Z_m Z m 鍵空間の大きさ:∣ K ∣ = m ! = 1 ⋅ 2 ⋅ ⋯ ⋅ m |K| = m! = 1 \cdot 2 \cdot \cdots \cdot m ∣ K ∣ = m ! = 1 ⋅ 2 ⋅ ⋯ ⋅ m
π ∈ K \pi \in K π ∈ K e π ( x 1 , ⋯ , x m ) : = x π ( 1 ) , ⋯ , x π ( m ) e_{\pi}(x_1, \cdots, x_m) := x_{\pi(1)}, \cdots, x_{\pi(m)} e π ( x 1 , ⋯ , x m ) : = x π ( 1 ) , ⋯ , x π ( m ) d π ( y 1 , ⋯ , y m ) : = y π − 1 ( 1 ) , ⋯ , y π − 1 ( m ) d_{\pi}(y_1, \cdots, y_m) := y_{\pi^{-1}(1)}, \cdots, y_{\pi^{-1}(m)} d π ( y 1 , ⋯ , y m ) : = y π − 1 ( 1 ) , ⋯ , y π − 1 ( m )
換字暗号では、文字の統計的性質(出現頻度)を利用することで解読される可能性
p ( e ) = 0.127 , p ( t ) = 0.91 , p ( a ) = 0.82 , ⋯ , p ( z ) = 0.063 p(e) = 0.127, p(t) = 0.91, p(a) = 0.82, \cdots, p(z) = 0.063 p ( e ) = 0 . 1 2 7 , p ( t ) = 0 . 9 1 , p ( a ) = 0 . 8 2 , ⋯ , p ( z ) = 0 . 0 6 3
転置暗号では、文字の連続する文字の出現頻度(bigram, trigram)を利用することで解読される可能性
頻出する文字の並び: bigram: th, he, in, er, an, re, ed \quad
計算量的安全性
暗号系を破るための既存の最も高速な方法をもってしても途方もなく莫大な計算時間を必要となるとき安全と考える
計算機の能力や攻撃法の発展で破られる可能性
現代暗号の安全性の基本となっている
情報理論的安全性
無限の計算資源を用いても破ることができないとき安全と考える
C. Shannon, “Communication Theory of SecrecySystems”, 1949
定義：すべてのx ∈ P , y ∈ C x \in P, y \in C x ∈ P , y ∈ C P ( x ∣ y ) = P ( x ) \color{red}{P(x \ |\ y) = P(x)} P ( x ∣ y ) = P ( x ) y y y x x x x x x 情報理論的安全性 , あるいは, 完全守秘性 (perfect secrecy)をもつという
暗号文y ∈ C y \in C y ∈ C x ∈ P x \in P x ∈ P P ( x ∣ y ) \color{red}{P(x \ |\ y)} P ( x ∣ y ) P ( x ) \color{red}{P(x)} P ( x )
情報理論的安全性をもつ暗号について
定理: ∣ K ∣ = ∣ P ∣ = ∣ C ∣ |K| = |P| = |C| ∣ K ∣ = ∣ P ∣ = ∣ C ∣ 1 ∣ K ∣ \frac{1}{|K|} ∣ K ∣ 1 x ∈ P , y ∈ C x \in P, y \in C x ∈ P , y ∈ C e k ( x ) = y \color{red}{e_k(x) = y} e k ( x ) = y 唯一の鍵 k ∈ K \color{red}{k \in K} k ∈ K 存在 するならば, その時に限り,この暗号系は完全秘匿性をもつ 。
定理: 情報理論的に安全な暗号系においては∣ K ∣ ≥ ∣ P ∣ \color{red}{|K| \geq |P|} ∣ K ∣ ≥ ∣ P ∣
1970年代以降, ネットワーク技術が発展し, 不特定多数の人がネットワークにアクセスできるようになり, ネットワーク上での情報通信の安全性（秘匿性）を考慮する必要
暗号化・復号の処理を容易に実現するために,誰でも利用できる標準の暗号が必要
標準暗号の設計思想
暗号アルゴリズムは公開
暗号の安全性は鍵によって確保(鍵が分からなければ、復号できない)
平文をデータ撹拌（かくはん）部において多段階に渡って部分鍵に基づいた撹拌を行うことで疑似ランダム性をもつ暗号文を生成する(撹拌部では、換字 と置換 を組み合わせる)
1976年にアメリカ連邦政府の標準暗号として採用された共通鍵暗号(データ：64ビット , 鍵：56ビット)
S-Boxを利用
コンピュータの性能向上により解読される可能性
TDES(Triple DES)：3鍵DES
異なる3つの鍵(k 1 , k 2 , k 3 k_1, k_2, k_3 k 1 , k 2 , k 3
DESの解読: 1998年 Deep Crack(DES解読コンピュータ)により22時間で解読
標準暗号であるDESの後継としてアメリカ政府が公募2001年にDaemen, Rijmen(ベルギー)が開発したRijndael(ラインドール）が採用される(選考に２年間余り)
データ長：128ビット
鍵長：128, 192, 256ビット
構造：SPN構造 (Substitution-Permutation Network)置換(Substitution)と転置(permutation)の組み合わせ（ネットワーク）により構成される
平文集合と鍵集合をP = K = { 0 , 1 , 2 , 3 , 4 } P = K = \lbrace 0, 1, 2, 3, 4 \rbrace P = K = { 0 , 1 , 2 , 3 , 4 } x ∈ P x \in P x ∈ P P r ( x = 0 ) = 1 3 , P r ( x = 1 ) = P r ( x = 2 ) = P r ( x = 3 ) = P r ( x = 4 ) = 1 6 Pr(x = 0) = \frac{1}{3}, Pr(x = 1) = Pr(x = 2) = Pr(x = 3) = Pr(x = 4) = \frac{1}{6} P r ( x = 0 ) = 3 1 , P r ( x = 1 ) = P r ( x = 2 ) = P r ( x = 3 ) = P r ( x = 4 ) = 6 1 P r ( c ) Pr(c) P r ( c ) P r ( x ∣ c ) Pr(x \ |\ c) P r ( x ∣ c ) P r ( k ) = 1 5 , k ∈ K Pr(k) = \frac{1}{5}, k \in K P r ( k ) = 5 1 , k ∈ K
(1) e k ( x ) = x + k m o d 5 e_k(x) = x + k \bmod 5 e k ( x ) = x + k m o d 5
C C C x = 0 x = 0 x = 0 x = 1 x = 1 x = 1 x = 2 x = 2 x = 2 x = 3 x = 3 x = 3 x = 4 x = 4 x = 4
k = 0 k = 0 k = 0 0
1
2
3
4
k = 1 k = 1 k = 1 1
2
3
4
5
k = 2 k = 2 k = 2 2
3
4
5
6
k = 3 k = 3 k = 3 3
4
5
6
7
k = 4 k = 4 k = 4 4
5
6
7
8
暗号文の確率分布P r ( c ) Pr(c) P r ( c )
P r ( c = 0 ) = 1 3 × 1 5 = 1 15 P r ( c = 1 ) = 1 3 × 1 5 + 1 6 × 1 5 = 1 10 P r ( c = 2 ) = 2 15 P r ( c = 3 ) = 1 6 P r ( c = 4 ) = 1 5 P r ( c = 5 ) = 2 15 P r ( c = 6 ) = 1 10 P r ( c = 7 ) = 1 15 P r ( c = 8 ) = 1 30 \begin{aligned}
&Pr(c = 0) = \frac{1}{3} \times \frac{1}{5} = \frac{1}{15}
\\
&Pr(c = 1) = \frac{1}{3} \times \frac{1}{5} + \frac{1}{6} \times \frac{1}{5} = \frac{1}{10}
\\
&Pr(c = 2) = \frac{2}{15}
\\
&Pr(c = 3) = \frac{1}{6}
\\
&Pr(c = 4) = \frac{1}{5}
\\
&Pr(c = 5) = \frac{2}{15}
\\
&Pr(c = 6) = \frac{1}{10}
\\
&Pr(c = 7) = \frac{1}{15}
\\
&Pr(c = 8) = \frac{1}{30}
\end{aligned}
P r ( c = 0 ) = 3 1 × 5 1 = 1 5 1 P r ( c = 1 ) = 3 1 × 5 1 + 6 1 × 5 1 = 1 0 1 P r ( c = 2 ) = 1 5 2 P r ( c = 3 ) = 6 1 P r ( c = 4 ) = 5 1 P r ( c = 5 ) = 1 5 2 P r ( c = 6 ) = 1 0 1 P r ( c = 7 ) = 1 5 1 P r ( c = 8 ) = 3 0 1
Bayesの定理により
P r ( P = x ∣ C = c ) = P r ( P = x ) ⋅ P r ( C = c ∣ P r ( P = x ) P r ( C = c ) = P r ( P = x ) ⋅ ∑ k , x = d k ( c ) P r ( K = k ) ∑ k , c ∈ c ( k ) P r ( K = k ) ⋅ P r ( x = d k ( c ) ) \begin{aligned}
Pr(P = x \ |\ C = c) &= \frac{Pr(P = x) \cdot Pr(C = c \ |\ Pr(P = x)}{Pr(C = c)}
\\
&= \frac{Pr(P = x) \cdot \sum_{k,x = d_k(c)} Pr(K = k)}{\sum_{k,c \in c(k)} Pr(K = k) \cdot Pr(x = d_k(c))}
\end{aligned}
P r ( P = x ∣ C = c ) = P r ( C = c ) P r ( P = x ) ⋅ P r ( C = c ∣ P r ( P = x ) = ∑ k , c ∈ c ( k ) P r ( K = k ) ⋅ P r ( x = d k ( c ) ) P r ( P = x ) ⋅ ∑ k , x = d k ( c ) P r ( K = k )
条件付き確率P r ( x ∣ c ) Pr(x \ |\ c) P r ( x ∣ c )
P r ( 0 ∣ 0 ) = 1 , P r ( 1 ∣ 0 ) = 0 , P r ( 2 ∣ 0 ) = 0 , P r ( 3 ∣ 0 ) = 0 , P r ( 4 ∣ 0 ) = 0 P r ( 0 ∣ 1 ) = 2 3 , P r ( 1 ∣ 1 ) = 1 3 , P r ( 2 ∣ 1 ) = 0 , P r ( 3 ∣ 1 ) = 0 , P r ( 4 ∣ 1 ) = 0 P r ( 0 ∣ 2 ) = 1 2 , P r ( 1 ∣ 2 ) = 1 4 , P r ( 2 ∣ 2 ) = 1 4 , P r ( 3 ∣ 2 ) = 0 , P r ( 4 ∣ 2 ) = 0 P r ( 0 ∣ 3 ) = 2 5 , P r ( 1 ∣ 3 ) = 1 5 , P r ( 2 ∣ 3 ) = 1 5 , P r ( 3 ∣ 3 ) = 1 5 , P r ( 4 ∣ 3 ) = 0 P r ( 0 ∣ 4 ) = 1 3 , P r ( 1 ∣ 4 ) = 1 6 , P r ( 2 ∣ 4 ) = 1 6 , P r ( 3 ∣ 4 ) = 1 6 , P r ( 4 ∣ 4 ) = 1 6 P r ( 0 ∣ 5 ) = 0 , P r ( 1 ∣ 5 ) = 1 4 , P r ( 2 ∣ 5 ) = 1 4 , P r ( 3 ∣ 5 ) = 1 4 , P r ( 4 ∣ 5 ) = 1 4 P r ( 0 ∣ 6 ) = 0 , P r ( 1 ∣ 6 ) = 0 , P r ( 2 ∣ 6 ) = 1 3 , P r ( 3 ∣ 6 ) = 1 3 , P r ( 4 ∣ 6 ) = 1 3 P r ( 0 ∣ 7 ) = 0 , P r ( 1 ∣ 7 ) = 0 , P r ( 2 ∣ 7 ) = 0 , P r ( 3 ∣ 7 ) = 1 2 , P r ( 4 ∣ 7 ) = 1 2 P r ( 0 ∣ 8 ) = 0 , P r ( 1 ∣ 8 ) = 0 , P r ( 2 ∣ 8 ) = 0 , P r ( 3 ∣ 8 ) = 0 , P r ( 4 ∣ 8 ) = 1 \begin{aligned}
&Pr(0 | 0) = 1, \quad Pr(1 | 0) = 0, \quad Pr(2 | 0) = 0,\quad Pr(3 | 0) = 0, \quad Pr(4 | 0) = 0
\\
\\
&Pr(0 | 1) = \frac{2}{3}, \quad Pr(1 | 1) = \frac{1}{3}, \quad Pr(2 | 1) = 0,\quad Pr(3 | 1) = 0, \quad Pr(4 | 1) = 0
\\
\\
&Pr(0 | 2) = \frac{1}{2}, \quad Pr(1 | 2) = \frac{1}{4}, \quad Pr(2 | 2) = \frac{1}{4},\quad Pr(3 | 2) = 0, \quad Pr(4 | 2) = 0
\\
\\
&Pr(0 | 3) = \frac{2}{5}, \quad Pr(1 | 3) = \frac{1}{5}, \quad Pr(2 | 3) = \frac{1}{5},\quad Pr(3 | 3) = \frac{1}{5}, \quad Pr(4 | 3) = 0
\\
\\
&Pr(0 | 4) = \frac{1}{3}, \quad Pr(1 | 4) = \frac{1}{6}, \quad Pr(2 | 4) = \frac{1}{6}, \quad Pr(3 | 4) = \frac{1}{6}, \quad Pr(4 | 4) = \frac{1}{6}
\\
\\
&Pr(0 | 5) = 0, \quad Pr(1 | 5) = \frac{1}{4}, \quad Pr(2 | 5) = \frac{1}{4}, \quad Pr(3 | 5) = \frac{1}{4}, \quad Pr(4 | 5) = \frac{1}{4}
\\
\\
&Pr(0 | 6) = 0, \quad Pr(1 | 6) = 0, \quad Pr(2 | 6) = \frac{1}{3}, \quad Pr(3 | 6) = \frac{1}{3}, \quad Pr(4 | 6) = \frac{1}{3}
\\
\\
&Pr(0 | 7) = 0, \quad Pr(1 | 7) = 0, \quad Pr(2 | 7) = 0, \quad Pr(3 | 7) = \frac{1}{2}, \quad Pr(4 | 7) = \frac{1}{2}
\\
\\
&Pr(0 | 8) = 0, \quad Pr(1 | 8) = 0, \quad Pr(2 | 8) = 0, \quad Pr(3 | 8) = 0, \quad Pr(4 | 8) = 1
\end{aligned}
P r ( 0 ∣ 0 ) = 1 , P r ( 1 ∣ 0 ) = 0 , P r ( 2 ∣ 0 ) = 0 , P r ( 3 ∣ 0 ) = 0 , P r ( 4 ∣ 0 ) = 0 P r ( 0 ∣ 1 ) = 3 2 , P r ( 1 ∣ 1 ) = 3 1 , P r ( 2 ∣ 1 ) = 0 , P r ( 3 ∣ 1 ) = 0 , P r ( 4 ∣ 1 ) = 0 P r ( 0 ∣ 2 ) = 2 1 , P r ( 1 ∣ 2 ) = 4 1 , P r ( 2 ∣ 2 ) = 4 1 , P r ( 3 ∣ 2 ) = 0 , P r ( 4 ∣ 2 ) = 0 P r ( 0 ∣ 3 ) = 5 2 , P r ( 1 ∣ 3 ) = 5 1 , P r ( 2 ∣ 3 ) = 5 1 , P r ( 3 ∣ 3 ) = 5 1 , P r ( 4 ∣ 3 ) = 0 P r ( 0 ∣ 4 ) = 3 1 , P r ( 1 ∣ 4 ) = 6 1 , P r ( 2 ∣ 4 ) = 6 1 , P r ( 3 ∣ 4 ) = 6 1 , P r ( 4 ∣ 4 ) = 6 1 P r ( 0 ∣ 5 ) = 0 , P r ( 1 ∣ 5 ) = 4 1 , P r ( 2 ∣ 5 ) = 4 1 , P r ( 3 ∣ 5 ) = 4 1 , P r ( 4 ∣ 5 ) = 4 1 P r ( 0 ∣ 6 ) = 0 , P r ( 1 ∣ 6 ) = 0 , P r ( 2 ∣ 6 ) = 3 1 , P r ( 3 ∣ 6 ) = 3 1 , P r ( 4 ∣ 6 ) = 3 1 P r ( 0 ∣ 7 ) = 0 , P r ( 1 ∣ 7 ) = 0 , P r ( 2 ∣ 7 ) = 0 , P r ( 3 ∣ 7 ) = 2 1 , P r ( 4 ∣ 7 ) = 2 1 P r ( 0 ∣ 8 ) = 0 , P r ( 1 ∣ 8 ) = 0 , P r ( 2 ∣ 8 ) = 0 , P r ( 3 ∣ 8 ) = 0 , P r ( 4 ∣ 8 ) = 1
(2) e k ( x ) = x + k e_k(x) = x + k e k ( x ) = x + k
C C C x = 0 x = 0 x = 0 x = 1 x = 1 x = 1 x = 2 x = 2 x = 2 x = 3 x = 3 x = 3 x = 4 x = 4 x = 4
k = 0 k = 0 k = 0 0
1
2
3
4
k = 1 k = 1 k = 1 1
2
3
4
5
k = 2 k = 2 k = 2 2
3
4
5
6
k = 3 k = 3 k = 3 3
4
5
6
7
k = 4 k = 4 k = 4 4
5
6
7
8
暗号文の確率分布P r ( c ) Pr(c) P r ( c )
P r ( c = 0 ) = 1 15 P r ( c = 1 ) = 1 10 P r ( c = 2 ) = 2 15 P r ( c = 3 ) = 1 6 P r ( c = 4 ) = 1 5 P r ( c = 5 ) = 2 15 P r ( c = 6 ) = 1 10 P r ( c = 7 ) = 1 15 P r ( c = 8 ) = 1 30 \begin{aligned}
&Pr(c = 0) = \frac{1}{15}
\\
&Pr(c = 1) = \frac{1}{10}
\\
&Pr(c = 2) = \frac{2}{15}
\\
&Pr(c = 3) = \frac{1}{6}
\\
&Pr(c = 4) = \frac{1}{5}
\\
&Pr(c = 5) = \frac{2}{15}
\\
&Pr(c = 6) = \frac{1}{10}
\\
&Pr(c = 7) = \frac{1}{15}
\\
&Pr(c = 8) = \frac{1}{30}
\end{aligned}
P r ( c = 0 ) = 1 5 1 P r ( c = 1 ) = 1 0 1 P r ( c = 2 ) = 1 5 2 P r ( c = 3 ) = 6 1 P r ( c = 4 ) = 5 1 P r ( c = 5 ) = 1 5 2 P r ( c = 6 ) = 1 0 1 P r ( c = 7 ) = 1 5 1 P r ( c = 8 ) = 3 0 1
Bayesの定理により条件付き確率P r ( x ∣ c ) Pr(x \ |\ c) P r ( x ∣ c )
P r ( 0 ∣ 0 ) = 1 , P r ( 1 ∣ 0 ) = 0 , P r ( 2 ∣ 0 ) = 0 , P r ( 3 ∣ 0 ) = 0 , P r ( 4 ∣ 0 ) = 0 P r ( 0 ∣ 1 ) = 2 3 , P r ( 1 ∣ 1 ) = 1 3 , P r ( 2 ∣ 1 ) = 0 , P r ( 3 ∣ 1 ) = 0 , P r ( 4 ∣ 1 ) = 0 P r ( 0 ∣ 2 ) = 1 2 , P r ( 1 ∣ 2 ) = 1 4 , P r ( 2 ∣ 2 ) = 1 4 , P r ( 3 ∣ 2 ) = 0 , P r ( 4 ∣ 2 ) = 0 P r ( 0 ∣ 3 ) = 2 5 , P r ( 1 ∣ 3 ) = 1 5 , P r ( 2 ∣ 3 ) = 1 5 , P r ( 3 ∣ 3 ) = 1 5 , P r ( 4 ∣ 3 ) = 0 P r ( 0 ∣ 4 ) = 1 3 , P r ( 1 ∣ 4 ) = 1 6 , P r ( 2 ∣ 4 ) = 1 6 , P r ( 3 ∣ 4 ) = 1 6 , P r ( 4 ∣ 4 ) = 1 6 P r ( 0 ∣ 5 ) = 0 , P r ( 1 ∣ 5 ) = 1 4 , P r ( 2 ∣ 5 ) = 1 4 , P r ( 3 ∣ 5 ) = 1 4 , P r ( 4 ∣ 5 ) = 1 4 P r ( 0 ∣ 6 ) = 0 , P r ( 1 ∣ 6 ) = 0 , P r ( 2 ∣ 6 ) = 1 3 , P r ( 3 ∣ 6 ) = 1 3 , P r ( 4 ∣ 6 ) = 1 3 P r ( 0 ∣ 7 ) = 0 , P r ( 1 ∣ 7 ) = 0 , P r ( 2 ∣ 7 ) = 0 , P r ( 3 ∣ 7 ) = 1 2 , P r ( 4 ∣ 7 ) = 1 2 P r ( 0 ∣ 8 ) = 0 , P r ( 1 ∣ 8 ) = 0 , P r ( 2 ∣ 8 ) = 0 , P r ( 3 ∣ 8 ) = 0 , P r ( 4 ∣ 8 ) = 1 \begin{aligned}
&Pr(0 | 0) = 1, \quad Pr(1 | 0) = 0, \quad Pr(2 | 0) = 0,\quad Pr(3 | 0) = 0, \quad Pr(4 | 0) = 0
\\
\\
&Pr(0 | 1) = \frac{2}{3}, \quad Pr(1 | 1) = \frac{1}{3}, \quad Pr(2 | 1) = 0,\quad Pr(3 | 1) = 0, \quad Pr(4 | 1) = 0
\\
\\
&Pr(0 | 2) = \frac{1}{2}, \quad Pr(1 | 2) = \frac{1}{4}, \quad Pr(2 | 2) = \frac{1}{4},\quad Pr(3 | 2) = 0, \quad Pr(4 | 2) = 0
\\
\\
&Pr(0 | 3) = \frac{2}{5}, \quad Pr(1 | 3) = \frac{1}{5}, \quad Pr(2 | 3) = \frac{1}{5},\quad Pr(3 | 3) = \frac{1}{5}, \quad Pr(4 | 3) = 0
\\
\\
&Pr(0 | 4) = \frac{1}{3}, \quad Pr(1 | 4) = \frac{1}{6}, \quad Pr(2 | 4) = \frac{1}{6}, \quad Pr(3 | 4) = \frac{1}{6}, \quad Pr(4 | 4) = \frac{1}{6}
\\
\\
&Pr(0 | 5) = 0, \quad Pr(1 | 5) = \frac{1}{4}, \quad Pr(2 | 5) = \frac{1}{4}, \quad Pr(3 | 5) = \frac{1}{4}, \quad Pr(4 | 5) = \frac{1}{4}
\\
\\
&Pr(0 | 6) = 0, \quad Pr(1 | 6) = 0, \quad Pr(2 | 6) = \frac{1}{3}, \quad Pr(3 | 6) = \frac{1}{3}, \quad Pr(4 | 6) = \frac{1}{3}
\\
\\
&Pr(0 | 7) = 0, \quad Pr(1 | 7) = 0, \quad Pr(2 | 7) = 0, \quad Pr(3 | 7) = \frac{1}{2}, \quad Pr(4 | 7) = \frac{1}{2}
\\
\\
&Pr(0 | 8) = 0, \quad Pr(1 | 8) = 0, \quad Pr(2 | 8) = 0, \quad Pr(3 | 8) = 0, \quad Pr(4 | 8) = 1
\end{aligned}
P r ( 0 ∣ 0 ) = 1 , P r ( 1 ∣ 0 ) = 0 , P r ( 2 ∣ 0 ) = 0 , P r ( 3 ∣ 0 ) = 0 , P r ( 4 ∣ 0 ) = 0 P r ( 0 ∣ 1 ) = 3 2 , P r ( 1 ∣ 1 ) = 3 1 , P r ( 2 ∣ 1 ) = 0 , P r ( 3 ∣ 1 ) = 0 , P r ( 4 ∣ 1 ) = 0 P r ( 0 ∣ 2 ) = 2 1 , P r ( 1 ∣ 2 ) = 4 1 , P r ( 2 ∣ 2 ) = 4 1 , P r ( 3 ∣ 2 ) = 0 , P r ( 4 ∣ 2 ) = 0 P r ( 0 ∣ 3 ) = 5 2 , P r ( 1 ∣ 3 ) = 5 1 , P r ( 2 ∣ 3 ) = 5 1 , P r ( 3 ∣ 3 ) = 5 1 , P r ( 4 ∣ 3 ) = 0 P r ( 0 ∣ 4 ) = 3 1 , P r ( 1 ∣ 4 ) = 6 1 , P r ( 2 ∣ 4 ) = 6 1 , P r ( 3 ∣ 4 ) = 6 1 , P r ( 4 ∣ 4 ) = 6 1 P r ( 0 ∣ 5 ) = 0 , P r ( 1 ∣ 5 ) = 4 1 , P r ( 2 ∣ 5 ) = 4 1 , P r ( 3 ∣ 5 ) = 4 1 , P r ( 4 ∣ 5 ) = 4 1 P r ( 0 ∣ 6 ) = 0 , P r ( 1 ∣ 6 ) = 0 , P r ( 2 ∣ 6 ) = 3 1 , P r ( 3 ∣ 6 ) = 3 1 , P r ( 4 ∣ 6 ) = 3 1 P r ( 0 ∣ 7 ) = 0 , P r ( 1 ∣ 7 ) = 0 , P r ( 2 ∣ 7 ) = 0 , P r ( 3 ∣ 7 ) = 2 1 , P r ( 4 ∣ 7 ) = 2 1 P r ( 0 ∣ 8 ) = 0 , P r ( 1 ∣ 8 ) = 0 , P r ( 2 ∣ 8 ) = 0 , P r ( 3 ∣ 8 ) = 0 , P r ( 4 ∣ 8 ) = 1
一般に取り扱われるデータ（平文）の長さはブロック暗号のデータ長を超えるため、利用するブロック暗号のデータ長ごとにデータ（平文）を分割して暗号化する必要がある
ECBモードは同一鍵を用いて、各ブロックを暗号化し、復号の際も同じ鍵を用いて、各ブロックを復号する
同一の平文が入力されたとき、暗号文も同一となるそのため、統計的な解析等で推測がしやすくなる（画像のようなデータの場合、同じ値が続くことがある）
1ビット誤りの伝搬: 1ブロック
並列計算: 実行可能
暗号化では、乱数を用いて初期値r r r r r r x i x_i x i c i − 1 c_{i-1} c i − 1 排他的論理和 を取り、その値を暗号化鍵k k k c i c_i c i x 1 x_1 x 1 c 0 c_0 c 0 r r r
復号では、暗号文ブロックc i c_i c i c i − 1 c_{i-1} c i − 1 排他的論理和 を取り、元の平文ブロックx i x_i x i
最も良く使用されているモードであり、標準実装されている場合が多い
初期値は定数を用いると安全でなくなる
1ビット誤りの伝搬: 1ブロック+次のブロックの1ビット
並列計算: 暗号化は実行不可、復号は実行可能
排他的論理和x ⊕ y x \oplus y x ⊕ y
x , y x,y x , y 各ビットごとに下記の表にある計算を実行
計算結果を元の数値に変換
暗号化、復号共CBCモードと同様に初期値r r r r r r c i − 1 c_{i-1} c i − 1 k k k x i x_i x i 排他的論理和 を取り、暗号文ブロックc i c_i c i x 1 x_1 x 1 c 0 c_0 c 0 r r r
復号では、ひとつ前の暗号文ブロックc i − 1 c_{i-1} c i − 1 k k k c i c_i c i 排他的論理和 を取り、元の平文ブロックx i x_i x i
暗号化処理のみで実現可能
1ビット誤りの伝搬: 1ブロック+次のブロックに影響
並列計算: 暗号化は実行不可、復号は実行可能
OFBモード暗号化はCFBモードと似た形になっているが、次のブロック送るのは排他的論理和 を取る前の暗号化した値のみになる。r 0 r_0 r 0 r r r r i r_i r i r i − 1 r_{i-1} r i − 1 r i r_i r i r r r r i r_i r i x i x_i x i 排他的論理和 を取り、暗号化できる。
これらの計算は復号も同様になる。すなわち、OFBモードの暗号化、復号の処理は入力が異なるだけで、全く同じものになる。
暗号化処理のみで実現可能
暗号化と復号が同じ処理
ビット誤りによる影響が最小限であるので、無線通信のようなエラーレートが高い通信路にも適する
1ビット誤りの伝搬: 1ビットのみ
並列計算： 暗号化・復号初期値が既知であれば事前計算可能
シフト暗号: e k ( x ) = x + k m o d n , n = 32 e_k(x) = x + k \bmod n, \quad n = 32 e k ( x ) = x + k m o d n , n = 3 2 k = 7 k = 7 k = 7 ⇒ ( x 1 , x 2 , x 3 , x 4 ) = ( 10 , 8 , 13 , 6 ) \Rightarrow (x_1, x_2, x_3, x_4) = (10, 8, 13, 6) ⇒ ( x 1 , x 2 , x 3 , x 4 ) = ( 1 0 , 8 , 1 3 , 6 )
c 1 = e k ( x 1 ) = 10 + 7 m o d 32 = 17 c 2 = e k ( x 2 ) = 8 + 7 m o d 32 = 15 c 3 = e k ( x 3 ) = 13 + 7 m o d 32 = 20 c 4 = e k ( x 4 ) = 6 + 7 m o d 32 = 13 \begin{aligned}
&c_1 = e_k(x_1) = 10 + 7 \bmod 32 = 17
\\
&c_2 = e_k(x_2) = 8 + 7 \bmod 32 = 15
\\
&c_3 = e_k(x_3) = 13 + 7 \bmod 32 = 20
\\
&c_4 = e_k(x_4) = 6 + 7 \bmod 32 = 13
\end{aligned}
c 1 = e k ( x 1 ) = 1 0 + 7 m o d 3 2 = 1 7 c 2 = e k ( x 2 ) = 8 + 7 m o d 3 2 = 1 5 c 3 = e k ( x 3 ) = 1 3 + 7 m o d 3 2 = 2 0 c 4 = e k ( x 4 ) = 6 + 7 m o d 3 2 = 1 3
暗号文: rpun
c 1 = e k ( x 1 ⊕ c 0 ) = ( 10 ⊕ 13 ) + 7 m o d 32 = 14 c 2 = e k ( x 2 ⊕ c 1 ) = ( 8 ⊕ 14 ) + 7 m o d 32 = 13 c 3 = e k ( x 3 ⊕ c 2 ) = ( 13 ⊕ 13 ) + 7 m o d 32 = 7 c 4 = e k ( x 4 ⊕ c 3 ) = ( 6 ⊕ 7 ) + 7 m o d 32 = 8 \begin{aligned}
&c_1 = e_k(x_1 \oplus c_0) = (10 \oplus 13) + 7 \bmod 32 = 14
\\
&c_2 = e_k(x_2 \oplus c_1) = (8 \oplus 14) + 7 \bmod 32 = 13
\\
&c_3 = e_k(x_3 \oplus c_2) = (13 \oplus 13) + 7 \bmod 32 = 7
\\
&c_4 = e_k(x_4 \oplus c_3) = (6 \oplus 7) + 7 \bmod 32 = 8
\end{aligned}
c 1 = e k ( x 1 ⊕ c 0 ) = ( 1 0 ⊕ 1 3 ) + 7 m o d 3 2 = 1 4 c 2 = e k ( x 2 ⊕ c 1 ) = ( 8 ⊕ 1 4 ) + 7 m o d 3 2 = 1 3 c 3 = e k ( x 3 ⊕ c 2 ) = ( 1 3 ⊕ 1 3 ) + 7 m o d 3 2 = 7 c 4 = e k ( x 4 ⊕ c 3 ) = ( 6 ⊕ 7 ) + 7 m o d 3 2 = 8
暗号文: onhi
x 1 = d k ( c 1 ) ⊕ c 0 = ( 14 − 7 m o d 32 ) ⊕ 13 = 10 x 2 = d k ( c 2 ) ⊕ c 1 = ( 13 − 7 m o d 32 ) ⊕ 14 = 8 x 3 = d k ( c 3 ) ⊕ c 2 = ( 7 − 7 m o d 32 ) ⊕ 13 = 13 x 4 = d k ( c 4 ) ⊕ c 3 = ( 8 − 7 m o d 32 ) ⊕ 7 = 6 \begin{aligned}
&x_1 = d_k(c_1) \oplus c_0 = (14 - 7 \bmod 32) \oplus 13 = 10
\\
&x_2 = d_k(c_2) \oplus c_1 = (13 - 7 \bmod 32) \oplus 14 = 8
\\
&x_3 = d_k(c_3) \oplus c_2 = (7 - 7 \bmod 32) \oplus 13 = 13
\\
&x_4 = d_k(c_4) \oplus c_3 = (8 - 7 \bmod 32) \oplus 7 = 6
\end{aligned}
x 1 = d k ( c 1 ) ⊕ c 0 = ( 1 4 − 7 m o d 3 2 ) ⊕ 1 3 = 1 0 x 2 = d k ( c 2 ) ⊕ c 1 = ( 1 3 − 7 m o d 3 2 ) ⊕ 1 4 = 8 x 3 = d k ( c 3 ) ⊕ c 2 = ( 7 − 7 m o d 3 2 ) ⊕ 1 3 = 1 3 x 4 = d k ( c 4 ) ⊕ c 3 = ( 8 − 7 m o d 3 2 ) ⊕ 7 = 6
平文: king
c 1 = x 1 ⊕ e k ( c 0 ) = 10 ⊕ ( 13 + 7 m o d 32 ) = 30 c 2 = x 2 ⊕ e k ( c 1 ) = 8 ⊕ ( 30 + 7 m o d 32 ) = 13 c 3 = x 3 ⊕ e k ( c 2 ) = 13 ⊕ ( 13 + 7 m o d 32 ) = 25 c 4 = x 4 ⊕ e k ( c 3 ) = 6 ⊕ ( 25 + 7 m o d 32 ) = 6 \begin{aligned}
&c_1 = x_1 \oplus e_k(c_0) = 10 \oplus (13 + 7 \bmod 32) = 30
\\
&c_2 = x_2 \oplus e_k(c_1) = 8 \oplus (30 + 7 \bmod 32) = 13
\\
&c_3 = x_3 \oplus e_k(c_2) = 13 \oplus (13 + 7 \bmod 32) = 25
\\
&c_4 = x_4 \oplus e_k(c_3) = 6 \oplus (25 + 7 \bmod 32) = 6
\end{aligned}
c 1 = x 1 ⊕ e k ( c 0 ) = 1 0 ⊕ ( 1 3 + 7 m o d 3 2 ) = 3 0 c 2 = x 2 ⊕ e k ( c 1 ) = 8 ⊕ ( 3 0 + 7 m o d 3 2 ) = 1 3 c 3 = x 3 ⊕ e k ( c 2 ) = 1 3 ⊕ ( 1 3 + 7 m o d 3 2 ) = 2 5 c 4 = x 4 ⊕ e k ( c 3 ) = 6 ⊕ ( 2 5 + 7 m o d 3 2 ) = 6
暗号文: =nzg
x 1 = c 1 ⊕ e k ( c 0 ) = 30 ⊕ ( 13 + 7 m o d 32 ) = 10 x 2 = c 2 ⊕ e k ( c 1 ) = 13 ⊕ ( 30 + 7 m o d 32 ) = 8 x 3 = c 3 ⊕ e k ( c 2 ) = 25 ⊕ ( 13 + 7 m o d 32 ) = 13 x 4 = c 4 ⊕ e k ( c 3 ) = 6 ⊕ ( 25 + 7 m o d 32 ) = 6 \begin{aligned}
&x_1 = c_1 \oplus e_k(c_0) = 30 \oplus (13 + 7 \bmod 32) = 10
\\
&x_2 = c_2 \oplus e_k(c_1) = 13 \oplus (30 + 7 \bmod 32) = 8
\\
&x_3 = c_3 \oplus e_k(c_2) = 25 \oplus (13 + 7 \bmod 32) = 13
\\
&x_4 = c_4 \oplus e_k(c_3) = 6 \oplus (25 + 7 \bmod 32) = 6
\end{aligned}
x 1 = c 1 ⊕ e k ( c 0 ) = 3 0 ⊕ ( 1 3 + 7 m o d 3 2 ) = 1 0 x 2 = c 2 ⊕ e k ( c 1 ) = 1 3 ⊕ ( 3 0 + 7 m o d 3 2 ) = 8 x 3 = c 3 ⊕ e k ( c 2 ) = 2 5 ⊕ ( 1 3 + 7 m o d 3 2 ) = 1 3 x 4 = c 4 ⊕ e k ( c 3 ) = 6 ⊕ ( 2 5 + 7 m o d 3 2 ) = 6
平文: king
c 1 = x 1 ⊕ e k ( r 0 ) = 10 ⊕ ( 13 + 7 m o d 32 ) = 30 c 2 = x 2 ⊕ e k ( r 1 ) = 8 ⊕ ( 20 + 7 m o d 32 ) = 19 c 3 = x 3 ⊕ e k ( r 2 ) = 13 ⊕ ( 27 + 7 m o d 32 ) = 15 c 4 = x 4 ⊕ e k ( r 3 ) = 6 ⊕ ( 2 + 7 m o d 32 ) = 15 \begin{aligned}
&c_1 = x_1 \oplus e_k(r_0) = 10 \oplus (13 + 7 \bmod 32) = 30
\\
&c_2 = x_2 \oplus e_k(r_1) = 8 \oplus (\color{blue}{20} + 7 \bmod 32) = 19
\\
&c_3 = x_3 \oplus e_k(r_2) = 13 \oplus (\color{blue}{27} + 7 \bmod 32) = 15
\\
&c_4 = x_4 \oplus e_k(r_3) = 6 \oplus (\color{blue}{2} + 7 \bmod 32) = 15
\end{aligned}
c 1 = x 1 ⊕ e k ( r 0 ) = 1 0 ⊕ ( 1 3 + 7 m o d 3 2 ) = 3 0 c 2 = x 2 ⊕ e k ( r 1 ) = 8 ⊕ ( 2 0 + 7 m o d 3 2 ) = 1 9 c 3 = x 3 ⊕ e k ( r 2 ) = 1 3 ⊕ ( 2 7 + 7 m o d 3 2 ) = 1 5 c 4 = x 4 ⊕ e k ( r 3 ) = 6 ⊕ ( 2 + 7 m o d 3 2 ) = 1 5
暗号文: =tpp
x 1 = c 1 ⊕ e k ( r 0 ) = 30 ⊕ ( 13 + 7 m o d 32 ) = 10 x 2 = c 2 ⊕ e k ( r 1 ) = 19 ⊕ ( 20 + 7 m o d 32 ) = 8 x 3 = c 3 ⊕ e k ( r 2 ) = 15 ⊕ ( 27 + 7 m o d 32 ) = 13 x 4 = c 4 ⊕ e k ( r 3 ) = 15 ⊕ ( 2 + 7 m o d 32 ) = 6 \begin{aligned}
&x_1 = c_1 \oplus e_k(r_0) = 30 \oplus (13 + 7 \bmod 32) = 10
\\
&x_2 = c_2 \oplus e_k(r_1) = 19 \oplus (\color{blue}{20} + 7 \bmod 32) = 8
\\
&x_3 = c_3 \oplus e_k(r_2) = 15 \oplus (\color{blue}{27} + 7 \bmod 32) = 13
\\
&x_4 = c_4 \oplus e_k(r_3) = 15 \oplus (\color{blue}{2} + 7 \bmod 32) = 6
\end{aligned}
x 1 = c 1 ⊕ e k ( r 0 ) = 3 0 ⊕ ( 1 3 + 7 m o d 3 2 ) = 1 0 x 2 = c 2 ⊕ e k ( r 1 ) = 1 9 ⊕ ( 2 0 + 7 m o d 3 2 ) = 8 x 3 = c 3 ⊕ e k ( r 2 ) = 1 5 ⊕ ( 2 7 + 7 m o d 3 2 ) = 1 3 x 4 = c 4 ⊕ e k ( r 3 ) = 1 5 ⊕ ( 2 + 7 m o d 3 2 ) = 6
平文: king
CMAC(Cipher based Message Authentication Code)
メッセージの完全性を保証するために利用
モード
並列化
１ビット誤りの伝搬
特徴
ECB
可能
1ブロック
同一平文が同一暗号文に
CBC
暗号化：不可 \quad
１ブロック + 次ブロック１ビット
最も使用
CFB
暗号化：不可 \quad
1ビット + 次のブロック
暗号器のみ
OFB
事前計算可能（初期値既知）
1ビット
暗号器のみ \quad
平文集合と暗号文集合P = C = Z 32 P = C = Z_{32} P = C = Z 3 2 e k 1 , k 2 ( x ) = k 1 x + k 2 m o d 32 e_{k_1,k_2}(x) = k_1x + k_2 \bmod 32 e k 1 , k 2 ( x ) = k 1 x + k 2 m o d 3 2
なお、アフィン暗号の復号はd k 1 , k 2 ( y ) = k 1 − 1 ( y − k 2 ) m o d 32 d_{k_1, k_2}(y) = k_1^{-1} (y - k_2) \bmod 32 d k 1 , k 2 ( y ) = k 1 − 1 ( y − k 2 ) m o d 3 2 5 − 1 ≡ 13 m o d 32 ( 5 × 13 ≡ 1 m o d 32 ) 5^{-1} \equiv 13 \bmod 32(5 \times 13 \equiv 1 \bmod 32) 5 − 1 ≡ 1 3 m o d 3 2 ( 5 × 1 3 ≡ 1 m o d 3 2 )
暗号化鍵は( k 1 , k 2 ) = ( 5 , 17 ) (k_1, k_2) = (5, 17) ( k 1 , k 2 ) = ( 5 , 1 7 )
ECBモード
暗号:c i = e k ( x i ) c_i = e_k(x_i) c i = e k ( x i )
復号:x i = d k ( c i ) x_i = d_k(c_i) x i = d k ( c i )
c 1 = e k 1 , k 2 ( x 1 ) = 5 × 16 + 17 m o d 32 = 1 c 2 = e k 1 , k 2 ( x 2 ) = 5 × 20 + 17 m o d 32 = 21 c 3 = e k 1 , k 2 ( x 3 ) = 5 × 4 + 17 m o d 32 = 5 c 4 = e k 1 , k 2 ( x 4 ) = 5 × 4 + 17 m o d 32 = 5 c 5 = e k 1 , k 2 ( x 5 ) = 5 × 13 + 17 m o d 32 = 18 \begin{aligned}
&c_1 = e_{k_1, k_2}(x_1) = 5 \times 16 + 17 \bmod 32 = 1
\\
&c_2 = e_{k_1, k_2}(x_2) = 5 \times 20 + 17 \bmod 32 = 21
\\
&c_3 = e_{k_1, k_2}(x_3) = 5 \times 4 + 17 \bmod 32 = 5
\\
&c_4 = e_{k_1, k_2}(x_4) = 5 \times 4 + 17 \bmod 32 = 5
\\
&c_5 = e_{k_1, k_2}(x_5) = 5 \times 13 + 17 \bmod 32 = 18
\end{aligned}
c 1 = e k 1 , k 2 ( x 1 ) = 5 × 1 6 + 1 7 m o d 3 2 = 1 c 2 = e k 1 , k 2 ( x 2 ) = 5 × 2 0 + 1 7 m o d 3 2 = 2 1 c 3 = e k 1 , k 2 ( x 3 ) = 5 × 4 + 1 7 m o d 3 2 = 5 c 4 = e k 1 , k 2 ( x 4 ) = 5 × 4 + 1 7 m o d 3 2 = 5 c 5 = e k 1 , k 2 ( x 5 ) = 5 × 1 3 + 1 7 m o d 3 2 = 1 8
暗号文: bvffs
x 1 = d k 1 , k 2 ( c 1 ) = 5 − 1 ( 1 − 17 ) m o d 32 = 13 × 16 m o d 32 = 16 x 2 = d k 1 , k 2 ( c 2 ) = 5 − 1 ( 21 − 17 ) m o d 32 = 13 × 4 m o d 32 = 20 x 3 = d k 1 , k 2 ( c 3 ) = 5 − 1 ( 5 − 17 ) m o d 32 = 13 × 20 m o d 32 = 4 x 4 = d k 1 , k 2 ( c 4 ) = 5 − 1 ( 5 − 17 ) m o d 32 = 13 × 20 m o d 32 = 4 x 5 = d k 1 , k 2 ( c 5 ) = 5 − 1 ( 18 − 17 ) m o d 32 = 13 × 1 m o d 32 = 13 \begin{aligned}
&x_1 = d_{k_1, k_2}(c_1) = 5^{-1}(1 - 17) \bmod 32 = 13 \times 16 \bmod 32 = 16
\\
&x_2 = d_{k_1, k_2}(c_2) = 5^{-1}(21 - 17) \bmod 32 = 13 \times 4 \bmod 32 = 20
\\
&x_3 = d_{k_1, k_2}(c_3) = 5^{-1}(5 - 17) \bmod 32 = 13 \times 20 \bmod 32 = 4
\\
&x_4 = d_{k_1, k_2}(c_4) = 5^{-1}(5 - 17) \bmod 32 = 13 \times 20 \bmod 32 = 4
\\
&x_5 = d_{k_1, k_2}(c_5) = 5^{-1}(18 - 17) \bmod 32 = 13 \times 1 \bmod 32 = 13
\end{aligned}
x 1 = d k 1 , k 2 ( c 1 ) = 5 − 1 ( 1 − 1 7 ) m o d 3 2 = 1 3 × 1 6 m o d 3 2 = 1 6 x 2 = d k 1 , k 2 ( c 2 ) = 5 − 1 ( 2 1 − 1 7 ) m o d 3 2 = 1 3 × 4 m o d 3 2 = 2 0 x 3 = d k 1 , k 2 ( c 3 ) = 5 − 1 ( 5 − 1 7 ) m o d 3 2 = 1 3 × 2 0 m o d 3 2 = 4 x 4 = d k 1 , k 2 ( c 4 ) = 5 − 1 ( 5 − 1 7 ) m o d 3 2 = 1 3 × 2 0 m o d 3 2 = 4 x 5 = d k 1 , k 2 ( c 5 ) = 5 − 1 ( 1 8 − 1 7 ) m o d 3 2 = 1 3 × 1 m o d 3 2 = 1 3
復号の結果: queen
CBCモード
暗号: c i = e k ( x i ⊕ c i − 1 ) , c 0 = r c_i = e_k(x_i \oplus c_{i-1}), \quad c_0 = r c i = e k ( x i ⊕ c i − 1 ) , c 0 = r
復号: x i = d k ( c i ) ⊕ c i − 1 , c 0 = r x_i = d_k(c_i) \oplus c_{i-1}, \quad c_0 = r x i = d k ( c i ) ⊕ c i − 1 , c 0 = r
c 1 = e k 1 , k 2 ( x 1 ⊕ c 0 ) = k 1 ( 16 ⊕ 11 ) + k 2 m o d 32 = 5 × 27 + 17 m o d 32 = 24 c 2 = e k 1 , k 2 ( x 2 ⊕ c 1 ) = k 1 ( 20 ⊕ 24 ) + k 2 m o d 32 = 5 × 12 + 17 m o d 32 = 13 c 3 = e k 1 , k 2 ( x 3 ⊕ c 2 ) = k 1 ( 4 ⊕ 13 ) + k 2 m o d 32 = 5 × 9 + 17 m o d 32 = 30 c 4 = e k 1 , k 2 ( x 4 ⊕ c 3 ) = k 1 ( 4 ⊕ 30 ) + k 2 m o d 32 = 5 × 26 + 17 m o d 32 = 19 c 5 = e k 1 , k 2 ( x 5 ⊕ c 4 ) = k 1 ( 13 ⊕ 19 ) + k 2 m o d 32 = 5 × 30 + 17 m o d 32 = 7 \begin{aligned}
&c_1 = e_{k_1, k_2}(x_1 \oplus c_0) = k_1(16 \oplus 11) + k_2 \bmod 32 = 5 \times 27 + 17 \bmod 32 = 24
\\
&c_2 = e_{k_1, k_2}(x_2 \oplus c_1) = k_1(20 \oplus 24) + k_2 \bmod 32 = 5 \times 12 + 17 \bmod 32 = 13
\\
&c_3 = e_{k_1, k_2}(x_3 \oplus c_2) = k_1(4 \oplus 13) + k_2 \bmod 32 = 5 \times 9 + 17 \bmod 32 = 30
\\
&c_4 = e_{k_1, k_2}(x_4 \oplus c_3) = k_1(4 \oplus 30) + k_2 \bmod 32 = 5 \times 26 + 17 \bmod 32 = 19
\\
&c_5 = e_{k_1, k_2}(x_5 \oplus c_4) = k_1(13 \oplus 19) + k_2 \bmod 32 = 5 \times 30 + 17 \bmod 32 = 7
\end{aligned}
c 1 = e k 1 , k 2 ( x 1 ⊕ c 0 ) = k 1 ( 1 6 ⊕ 1 1 ) + k 2 m o d 3 2 = 5 × 2 7 + 1 7 m o d 3 2 = 2 4 c 2 = e k 1 , k 2 ( x 2 ⊕ c 1 ) = k 1 ( 2 0 ⊕ 2 4 ) + k 2 m o d 3 2 = 5 × 1 2 + 1 7 m o d 3 2 = 1 3 c 3 = e k 1 , k 2 ( x 3 ⊕ c 2 ) = k 1 ( 4 ⊕ 1 3 ) + k 2 m o d 3 2 = 5 × 9 + 1 7 m o d 3 2 = 3 0 c 4 = e k 1 , k 2 ( x 4 ⊕ c 3 ) = k 1 ( 4 ⊕ 3 0 ) + k 2 m o d 3 2 = 5 × 2 6 + 1 7 m o d 3 2 = 1 9 c 5 = e k 1 , k 2 ( x 5 ⊕ c 4 ) = k 1 ( 1 3 ⊕ 1 9 ) + k 2 m o d 3 2 = 5 × 3 0 + 1 7 m o d 3 2 = 7
暗号文: yn=th
x 1 = d k 1 , k 2 ( c 1 ) ⊕ c 0 = k 1 − 1 ( c 1 − k 2 ) m o d 32 ⊕ c 0 = 13 × 7 m o d 32 ⊕ 11 = 16 x 2 = d k 1 , k 2 ( c 2 ) ⊕ c 1 = k 1 − 1 ( c 1 − k 2 ) m o d 32 ⊕ c 1 = 13 × 28 m o d 32 ⊕ 24 = 20 x 3 = d k 1 , k 2 ( c 3 ) ⊕ c 2 = k 1 − 1 ( c 1 − k 2 ) m o d 32 ⊕ c 2 = 13 × 13 m o d 32 ⊕ 13 = 4 x 4 = d k 1 , k 2 ( c 4 ) ⊕ c 3 = k 1 − 1 ( c 1 − k 2 ) m o d 32 ⊕ c 3 = 13 × 2 m o d 32 ⊕ 30 = 4 x 5 = d k 1 , k 2 ( c 5 ) ⊕ c 4 = k 1 − 1 ( c 1 − k 2 ) m o d 32 ⊕ c 4 = 13 × 22 m o d 32 ⊕ 19 = 13 \begin{aligned}
&x_1 = d_{k_1, k_2}(c_1) \oplus c_0 = k_1^{-1}(c_1 - k_2) \bmod 32 \oplus c_0 = 13 \times 7 \bmod 32 \oplus 11 = 16
\\
&x_2 = d_{k_1, k_2}(c_2) \oplus c_1 = k_1^{-1}(c_1 - k_2) \bmod 32 \oplus c_1 = 13 \times 28 \bmod 32 \oplus 24 = 20
\\
&x_3 = d_{k_1, k_2}(c_3) \oplus c_2 = k_1^{-1}(c_1 - k_2) \bmod 32 \oplus c_2 = 13 \times 13 \bmod 32 \oplus 13 = 4
\\
&x_4 = d_{k_1, k_2}(c_4) \oplus c_3 = k_1^{-1}(c_1 - k_2) \bmod 32 \oplus c_3 = 13 \times 2 \bmod 32 \oplus 30 = 4
\\
&x_5 = d_{k_1, k_2}(c_5) \oplus c_4 = k_1^{-1}(c_1 - k_2) \bmod 32 \oplus c_4 = 13 \times 22 \bmod 32 \oplus 19 = 13
\end{aligned}
x 1 = d k 1 , k 2 ( c 1 ) ⊕ c 0 = k 1 − 1 ( c 1 − k 2 ) m o d 3 2 ⊕ c 0 = 1 3 × 7 m o d 3 2 ⊕ 1 1 = 1 6 x 2 = d k 1 , k 2 ( c 2 ) ⊕ c 1 = k 1 − 1 ( c 1 − k 2 ) m o d 3 2 ⊕ c 1 = 1 3 × 2 8 m o d 3 2 ⊕ 2 4 = 2 0 x 3 = d k 1 , k 2 ( c 3 ) ⊕ c 2 = k 1 − 1 ( c 1 − k 2 ) m o d 3 2 ⊕ c 2 = 1 3 × 1 3 m o d 3 2 ⊕ 1 3 = 4 x 4 = d k 1 , k 2 ( c 4 ) ⊕ c 3 = k 1 − 1 ( c 1 − k 2 ) m o d 3 2 ⊕ c 3 = 1 3 × 2 m o d 3 2 ⊕ 3 0 = 4 x 5 = d k 1 , k 2 ( c 5 ) ⊕ c 4 = k 1 − 1 ( c 1 − k 2 ) m o d 3 2 ⊕ c 4 = 1 3 × 2 2 m o d 3 2 ⊕ 1 9 = 1 3
復号の結果: queen
CFBモード
暗号: c i = x i ⊕ e k ( c i − 1 ) , c 0 = r c_i = x_i \oplus e_k(c_{i-1}), \quad c_0 = r c i = x i ⊕ e k ( c i − 1 ) , c 0 = r
復号: x i = c i ⊕ e k ( c i − 1 ) , c 0 = r x_i = c_i \oplus e_k(c_{i-1}), \quad c_0 = r x i = c i ⊕ e k ( c i − 1 ) , c 0 = r
c 1 = x 1 ⊕ e k 1 , k 2 ( c 0 ) = 16 ⊕ ( 55 + 17 m o d 32 ) = 24 c 2 = x 2 ⊕ e k 1 , k 2 ( c 1 ) = 20 ⊕ ( 120 + 17 m o d 32 ) = 29 c 3 = x 3 ⊕ e k 1 , k 2 ( c 2 ) = 4 ⊕ ( 145 + 17 m o d 32 ) = 6 c 4 = x 4 ⊕ e k 1 , k 2 ( c 3 ) = 4 ⊕ ( 30 + 17 m o d 32 ) = 11 c 5 = x 5 ⊕ e k 1 , k 2 ( c 4 ) = 13 ⊕ ( 55 + 17 m o d 32 ) = 5 \begin{aligned}
&c_1 = x_1 \oplus e_{k_1, k_2}(c_0) = 16 \oplus (55 + 17 \bmod 32) = 24
\\
&c_2 = x_2 \oplus e_{k_1, k_2}(c_1) = 20 \oplus (120 + 17 \bmod 32) = 29
\\
&c_3 = x_3 \oplus e_{k_1, k_2}(c_2) = 4 \oplus (145 + 17 \bmod 32) = 6
\\
&c_4 = x_4 \oplus e_{k_1, k_2}(c_3) = 4 \oplus (30 + 17 \bmod 32) = 11
\\
&c_5 = x_5 \oplus e_{k_1, k_2}(c_4) = 13 \oplus (55 + 17 \bmod 32) = 5
\end{aligned}
c 1 = x 1 ⊕ e k 1 , k 2 ( c 0 ) = 1 6 ⊕ ( 5 5 + 1 7 m o d 3 2 ) = 2 4 c 2 = x 2 ⊕ e k 1 , k 2 ( c 1 ) = 2 0 ⊕ ( 1 2 0 + 1 7 m o d 3 2 ) = 2 9 c 3 = x 3 ⊕ e k 1 , k 2 ( c 2 ) = 4 ⊕ ( 1 4 5 + 1 7 m o d 3 2 ) = 6 c 4 = x 4 ⊕ e k 1 , k 2 ( c 3 ) = 4 ⊕ ( 3 0 + 1 7 m o d 3 2 ) = 1 1 c 5 = x 5 ⊕ e k 1 , k 2 ( c 4 ) = 1 3 ⊕ ( 5 5 + 1 7 m o d 3 2 ) = 5
暗号文: y/glf
x 1 = c 1 ⊕ e k 1 , k 2 ( c 0 ) = 24 ⊕ ( 55 + 17 m o d 32 ) = 16 x 2 = c 2 ⊕ e k 1 , k 2 ( c 1 ) = 29 ⊕ ( 120 + 17 m o d 32 ) = 20 x 3 = c 3 ⊕ e k 1 , k 2 ( c 2 ) = 6 ⊕ ( 145 + 17 m o d 32 ) = 4 x 4 = c 4 ⊕ e k 1 , k 2 ( c 3 ) = 11 ⊕ ( 30 + 17 m o d 32 ) = 4 x 5 = c 5 ⊕ e k 1 , k 2 ( c 4 ) = 5 ⊕ ( 55 + 17 m o d 32 ) = 13 \begin{aligned}
&x_1 = c_1 \oplus e_{k_1, k_2}(c_0) = 24 \oplus (55 + 17 \bmod 32) = 16
\\
&x_2 = c_2 \oplus e_{k_1, k_2}(c_1) = 29 \oplus (120 + 17 \bmod 32) = 20
\\
&x_3 = c_3 \oplus e_{k_1, k_2}(c_2) = 6 \oplus (145 + 17 \bmod 32) = 4
\\
&x_4 = c_4 \oplus e_{k_1, k_2}(c_3) = 11 \oplus (30 + 17 \bmod 32) = 4
\\
&x_5 = c_5 \oplus e_{k_1, k_2}(c_4) = 5 \oplus (55 + 17 \bmod 32) = 13
\end{aligned}
x 1 = c 1 ⊕ e k 1 , k 2 ( c 0 ) = 2 4 ⊕ ( 5 5 + 1 7 m o d 3 2 ) = 1 6 x 2 = c 2 ⊕ e k 1 , k 2 ( c 1 ) = 2 9 ⊕ ( 1 2 0 + 1 7 m o d 3 2 ) = 2 0 x 3 = c 3 ⊕ e k 1 , k 2 ( c 2 ) = 6 ⊕ ( 1 4 5 + 1 7 m o d 3 2 ) = 4 x 4 = c 4 ⊕ e k 1 , k 2 ( c 3 ) = 1 1 ⊕ ( 3 0 + 1 7 m o d 3 2 ) = 4 x 5 = c 5 ⊕ e k 1 , k 2 ( c 4 ) = 5 ⊕ ( 5 5 + 1 7 m o d 3 2 ) = 1 3
復号の結果: queen
OFBモード
暗号: c i = x i ⊕ r i , r i = e k ( r i − 1 ) , r 0 = r c_i = x_i \oplus r_i, \quad r_i = e_k(r_{i-1}), \quad r_0 = r c i = x i ⊕ r i , r i = e k ( r i − 1 ) , r 0 = r
復号: x i = c i ⊕ r i , r i = e k ( r i − 1 ) , r 0 = r x_i = c_i \oplus r_i, \quad r_i = e_k(r_{i-1}), \quad r_0 = r x i = c i ⊕ r i , r i = e k ( r i − 1 ) , r 0 = r
c 1 = x 1 ⊕ e k 1 , k 2 ( r 0 ) = 16 ⊕ ( 5 × 11 + 17 m o d 32 ) = 16 ⊕ 8 = 24 c 2 = x 2 ⊕ e k 1 , k 2 ( r 1 ) = 20 ⊕ ( 5 × 8 + 17 m o d 32 ) = 20 ⊕ 25 = 13 c 3 = x 3 ⊕ e k 1 , k 2 ( r 2 ) = 4 ⊕ ( 5 × 25 + 17 m o d 32 ) = 4 ⊕ 14 = 10 c 4 = x 4 ⊕ e k 1 , k 2 ( r 3 ) = 4 ⊕ ( 5 × 14 + 17 m o d 32 ) = 4 ⊕ 23 = 19 c 5 = x 5 ⊕ e k 1 , k 2 ( r 4 ) = 13 ⊕ ( 5 × 23 + 17 m o d 32 ) = 13 ⊕ 4 = 9 \begin{aligned}
&c_1 = x_1 \oplus e_{k_1, k_2}(r_0) = 16 \oplus (5 \times 11 + 17 \bmod 32) = 16 \oplus 8 = 24
\\
&c_2 = x_2 \oplus e_{k_1, k_2}(r_1) = 20 \oplus (5 \times 8 + 17 \bmod 32) = 20 \oplus 25 = 13
\\
&c_3 = x_3 \oplus e_{k_1, k_2}(r_2) = 4 \oplus (5 \times 25 + 17 \bmod 32) = 4 \oplus 14 = 10
\\
&c_4 = x_4 \oplus e_{k_1, k_2}(r_3) = 4 \oplus (5 \times 14 + 17 \bmod 32) = 4 \oplus 23 = 19
\\
&c_5 = x_5 \oplus e_{k_1, k_2}(r_4) = 13 \oplus (5 \times 23 + 17 \bmod 32) = 13 \oplus 4 = 9
\end{aligned}
c 1 = x 1 ⊕ e k 1 , k 2 ( r 0 ) = 1 6 ⊕ ( 5 × 1 1 + 1 7 m o d 3 2 ) = 1 6 ⊕ 8 = 2 4 c 2 = x 2 ⊕ e k 1 , k 2 ( r 1 ) = 2 0 ⊕ ( 5 × 8 + 1 7 m o d 3 2 ) = 2 0 ⊕ 2 5 = 1 3 c 3 = x 3 ⊕ e k 1 , k 2 ( r 2 ) = 4 ⊕ ( 5 × 2 5 + 1 7 m o d 3 2 ) = 4 ⊕ 1 4 = 1 0 c 4 = x 4 ⊕ e k 1 , k 2 ( r 3 ) = 4 ⊕ ( 5 × 1 4 + 1 7 m o d 3 2 ) = 4 ⊕ 2 3 = 1 9 c 5 = x 5 ⊕ e k 1 , k 2 ( r 4 ) = 1 3 ⊕ ( 5 × 2 3 + 1 7 m o d 3 2 ) = 1 3 ⊕ 4 = 9
暗号文: ynktj
x 1 = c 1 ⊕ e k 1 , k 2 ( r 0 ) = 24 ⊕ ( 5 × 11 + 17 m o d 32 ) = 24 ⊕ 8 = 16 x 2 = c 2 ⊕ e k 1 , k 2 ( r 1 ) = 13 ⊕ ( 5 × 8 + 17 m o d 32 ) = 13 ⊕ 25 = 20 x 3 = c 3 ⊕ e k 1 , k 2 ( r 2 ) = 10 ⊕ ( 5 × 25 + 17 m o d 32 ) = 10 ⊕ 14 = 4 x 4 = c 4 ⊕ e k 1 , k 2 ( r 3 ) = 19 ⊕ ( 5 × 14 + 17 m o d 32 ) = 19 ⊕ 23 = 4 x 5 = c 5 ⊕ e k 1 , k 2 ( r 4 ) = 9 ⊕ ( 5 × 23 + 17 m o d 32 ) = 9 ⊕ 4 = 13 \begin{aligned}
&x_1 = c_1 \oplus e_{k_1, k_2}(r_0) = 24 \oplus (5 \times 11 + 17 \bmod 32) = 24 \oplus 8 = 16
\\
&x_2 = c_2 \oplus e_{k_1, k_2}(r_1) = 13 \oplus (5 \times 8 + 17 \bmod 32) = 13 \oplus 25 = 20
\\
&x_3 = c_3 \oplus e_{k_1, k_2}(r_2) = 10 \oplus (5 \times 25 + 17 \bmod 32) = 10 \oplus 14 = 4
\\
&x_4 = c_4 \oplus e_{k_1, k_2}(r_3) = 19 \oplus (5 \times 14 + 17 \bmod 32) = 19 \oplus 23 = 4
\\
&x_5 = c_5 \oplus e_{k_1, k_2}(r_4) = 9 \oplus (5 \times 23 + 17 \bmod 32) = 9 \oplus 4 = 13
\end{aligned}
x 1 = c 1 ⊕ e k 1 , k 2 ( r 0 ) = 2 4 ⊕ ( 5 × 1 1 + 1 7 m o d 3 2 ) = 2 4 ⊕ 8 = 1 6 x 2 = c 2 ⊕ e k 1 , k 2 ( r 1 ) = 1 3 ⊕ ( 5 × 8 + 1 7 m o d 3 2 ) = 1 3 ⊕ 2 5 = 2 0 x 3 = c 3 ⊕ e k 1 , k 2 ( r 2 ) = 1 0 ⊕ ( 5 × 2 5 + 1 7 m o d 3 2 ) = 1 0 ⊕ 1 4 = 4 x 4 = c 4 ⊕ e k 1 , k 2 ( r 3 ) = 1 9 ⊕ ( 5 × 1 4 + 1 7 m o d 3 2 ) = 1 9 ⊕ 2 3 = 4 x 5 = c 5 ⊕ e k 1 , k 2 ( r 4 ) = 9 ⊕ ( 5 × 2 3 + 1 7 m o d 3 2 ) = 9 ⊕ 4 = 1 3
復号の結果: queen
秘密である復号鍵k D k_D k D k E k_E k E k E k_E k E 一方向性関数 (One-Way Function)を利用共通鍵暗号のように秘密の鍵をお互いに交換する必要がなく、公開されている暗号化鍵を使って暗号化が可能
入力x 1 , x 2 , ⋯ , x n x_1, x_2, \cdots, x_n x 1 , x 2 , ⋯ , x n F ( x 1 , ⋯ , x n ) F(x_1, \cdots, x_n) F ( x 1 , ⋯ , x n ) F ( x 1 , ⋯ , x n ) F(x_1, \cdots, x_n) F ( x 1 , ⋯ , x n ) x 1 , ⋯ , x n x_1, \cdots, x_n x 1 , ⋯ , x n 計算量的に 困難である関数
代表的な一方向性関数:
素因数分解: 大きな素数p , q ⇄ n = p × q p, q \rightleftarrows n = p \times q p , q ⇄ n = p × q
離散対数問題：x x x g , n g, n g , n ⇄ y = g x m o d n \rightleftarrows y = g^x \bmod n ⇄ y = g x m o d n
一方向性関数と公開鍵暗号方式
素因数分解
RSA暗号(1977) RSA-OAEP暗号
Rabin暗号(1979)
離散対数問題
ElGamal暗号(1982) Cramer-Shoup暗号
楕円暗号(1985)
ナップザック問題
線形符号の復号問題
共通鍵暗号では, n n n ( n 2 ) \binom{n}{2} ( 2 n ) n n n
公開鍵暗号方式の鍵の非対称性を利用して, 署名方式が構築できる
一方向性(OW : One-Wayness)
暗号文c = f ( x ) c = f(x) c = f ( x ) x = f − 1 ( c ) x = f^{-1}(c) x = f − 1 ( c )
強秘匿性(SS : Semantically Secure)
平文x x x
識別不可能性(IND :INDistingishability)
2つの平文x 1 , x 2 x_1, x_2 x 1 , x 2 c c c c c c x 1 , x 2 x_1, x_2 x 1 , x 2
頑健性(NM :Non-Malleability)
平文に対する暗号文をc = f ( x ) c = f(x) c = f ( x ) c c c x x x x ′ x^{'} x ′ c ′ c^{'} c ′
暗号文単独攻撃(CTA : CipherText only Attack)
既知平文攻撃(KPA : Known Plaintext Attack)
選択平文攻撃(CPA :Chosen Plaintext Attack)
攻撃者が自由に選んだ平文とそれに対応する暗号文の両方を入手可能
選択暗号文攻撃(CCA :Chosen Ciphertext Attack)
攻撃者が自由に選んだ暗号文とそれに対応する平文の両方を入手可能
適応的選択暗号文攻撃(CCA2 )
CCAで暗号文を選ぶときに以前の復号の結果を利用することが可能
古典暗号
現代暗号までの暗号
OW-KPA
暗号化の方式は秘密
諜報活動等で平文が既知の場合もある
現代暗号
IND-CCA2
暗号化の方式は公開
公開鍵暗号は暗号化鍵が公開
攻撃者の強さは少なくともCPA
2つの整数 a , b ∈ Z a, b \in \mathbb{Z} a , b ∈ Z a − b a - b a − b n ∈ N n \in \mathbb{N} n ∈ N n n n
a ≡ b m o d n ⇔ a − b ∈ n Z : = { n × i ∣ i ∈ Z } a \equiv b \bmod n \Leftrightarrow a - b \in n\mathbb{Z} := \lbrace n \times i \ |\ i \in \mathbb{Z} \rbrace
a ≡ b m o d n ⇔ a − b ∈ n Z : = { n × i ∣ i ∈ Z }
剰余類 (residue class, coset)
n n n a a a
[ a ] : = a + n Z = { a + x ∣ x ∈ n Z } [a] := a + n\mathbb{Z} = \lbrace a + x \ |\ x \in n\mathbb{Z} \rbrace
[ a ] : = a + n Z = { a + x ∣ x ∈ n Z }
剰余類の集合
Z n : = Z n Z = { [ 0 ] , [ 1 ] , ⋯ , [ n − 1 ] } = { 0 , 1 , ⋯ , n − 1 } \mathbb{Z}_n := \frac{\mathbb{Z}}{n\mathbb{Z}} = \lbrace [0], [1], \cdots, [n-1] \rbrace = \lbrace 0, 1, \cdots, n-1 \rbrace
Z n : = n Z Z = { [ 0 ] , [ 1 ] , ⋯ , [ n − 1 ] } = { 0 , 1 , ⋯ , n − 1 }
例：剰余環n = 5 n = 5 n = 5
Z 5 = { [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] } = { 0 , 1 , 2 , 3 , 4 } \mathbb{Z}_5 = \lbrace [0], [1], [2], [3], [4] \rbrace = \lbrace 0, 1, 2, 3, 4 \rbrace
Z 5 = { [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] } = { 0 , 1 , 2 , 3 , 4 }
[ 0 ] = 0 + 5 Z = { ⋯ , − 10 , − 5 , 0 , 5 , 10 , ⋯ , } [ 1 ] = 1 + 5 Z = { ⋯ , − 9 , − 4 , 1 , 6 , 11 , ⋯ , } [ 2 ] = 2 + 5 Z = { ⋯ , − 8 , − 3 , 2 , 7 , 12 , ⋯ , } [ 3 ] = 3 + 5 Z = { ⋯ , − 7 , − 2 , 3 , 8 , 13 , ⋯ , } [ 4 ] = 4 + 5 Z = { ⋯ , − 6 , − 1 , 4 , 9 , 14 , ⋯ , } \begin{aligned}
&[0] = 0 + 5\mathbb{Z} = \lbrace \cdots, -10, -5, 0, 5, 10, \cdots, \rbrace
\\
&[1] = 1 + 5\mathbb{Z} = \lbrace \cdots, -9, -4, 1, 6, 11, \cdots, \rbrace
\\
&[2] = 2 + 5\mathbb{Z} = \lbrace \cdots, -8, -3, 2, 7, 12, \cdots, \rbrace
\\
&[3] = 3 + 5\mathbb{Z} = \lbrace \cdots, -7, -2, 3, 8, 13, \cdots, \rbrace
\\
&[4] = 4 + 5\mathbb{Z} = \lbrace \cdots, -6, -1, 4, 9, 14, \cdots, \rbrace
\end{aligned}
[ 0 ] = 0 + 5 Z = { ⋯ , − 1 0 , − 5 , 0 , 5 , 1 0 , ⋯ , } [ 1 ] = 1 + 5 Z = { ⋯ , − 9 , − 4 , 1 , 6 , 1 1 , ⋯ , } [ 2 ] = 2 + 5 Z = { ⋯ , − 8 , − 3 , 2 , 7 , 1 2 , ⋯ , } [ 3 ] = 3 + 5 Z = { ⋯ , − 7 , − 2 , 3 , 8 , 1 3 , ⋯ , } [ 4 ] = 4 + 5 Z = { ⋯ , − 6 , − 1 , 4 , 9 , 1 4 , ⋯ , }
F p \mathbb{F}_p F p N N N P P P Z p \mathbb{Z}_p Z p 体(Field) F p \mathbb{F}_p F p x ∈ F p / { 0 } x \in \mathbb{F}_p / \lbrace 0 \rbrace x ∈ F p / { 0 } x − 1 x^{-1} x − 1
n n n Z n \mathbb{Z}_n Z n 環 であり, 除算が定義できない(乗法に関する逆元がない要素が存在)
例: Z 6 \mathbb{Z}_6 Z 6 𝑛 = 6 𝑛 = 6 n = 6
2, 3, 4は掛けて1となる要素が存在しないため、逆元は存在しない
× \times × 1
2
3
4
5
1
1
2
3
4
5
2
2
4
0
2
4
3
3
0
3
0
3
4
4
2
0
4
2
5
5
4
3
2
1
n n n a a a n n n 既約剰余類 という.
Z n ∗ : = { a ∈ Z ∣ gcd ( a , n ) = 1 } \mathbb{Z}_n^* := \lbrace a \in \mathbb{Z} \ |\ \gcd(a, n) = 1 \rbrace
Z n ∗ : = { a ∈ Z ∣ g cd( a , n ) = 1 }
例:
Z 6 = { 0 , 1 , 2 , 3 , 4 , 5 } Z 6 ∗ = { 1 , 5 } Z 12 = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 } Z 12 ∗ = { 1 , 5 , 7 , 11 } \begin{aligned}
&\mathbb{Z}_6 = \lbrace 0, 1, 2, 3, 4, 5 \rbrace
\\
&\mathbb{Z}_6^* = \lbrace 1, 5 \rbrace
\\
\\
&\mathbb{Z}_{12} = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \rbrace
\\
&\mathbb{Z}_{12}^* = \lbrace 1, 5, 7, 11 \rbrace
\end{aligned}
Z 6 = { 0 , 1 , 2 , 3 , 4 , 5 } Z 6 ∗ = { 1 , 5 } Z 1 2 = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 0 , 1 1 } Z 1 2 ∗ = { 1 , 5 , 7 , 1 1 }
それぞれの逆元は自分自身になる
eg.5 × 5 − 1 = 1 → 5 − 1 = 5 5 \times 5^{-1} = 1 \rightarrow 5^{-1} = 5 5 × 5 − 1 = 1 → 5 − 1 = 5 gcd ( 12 , 5 ) = 1 \gcd(12, 5) = 1 g cd( 1 2 , 5 ) = 1
5 × 5 = 25 m o d 12 = 1 5 \times 5 = 25 \bmod 12 = 1 5 × 5 = 2 5 m o d 1 2 = 1 7 × 7 = 49 m o d 12 = 1 7 \times 7 = 49 \bmod 12 = 1 7 × 7 = 4 9 m o d 1 2 = 1 11 × 11 = 121 m o d 12 = 1 11 \times 11 = 121 \bmod 12 = 1 1 1 × 1 1 = 1 2 1 m o d 1 2 = 1
整数n n n gcd ( a , n ) = 1 \gcd(a, n) = 1 g cd( a , n ) = 1 a a a Z n ∗ \mathbb{Z}_n^* Z n ∗
整数m = p 1 e 1 ⋅ p 2 e 2 ⋯ p m e m m = p_1^{e_1} \cdot p_2^{e_2} \cdots p_m^{e_m} m = p 1 e 1 ⋅ p 2 e 2 ⋯ p m e m ϕ ( n ) \phi(n) ϕ ( n )
ϕ ( n ) = n ⋅ ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p m ) \phi(n) = n \cdot (1 - \frac{1}{p_1}) \cdots (1 - \frac{1}{p_m})
ϕ ( n ) = n ⋅ ( 1 − p 1 1 ) ⋯ ( 1 − p m 1 )
例: n = 12 = 2 2 ⋅ 3 1 n = 12 = 2^2 \cdot 3^1 n = 1 2 = 2 2 ⋅ 3 1
ϕ ( 12 ) = 12 ⋅ ( 1 − 1 2 ) ⋅ ( 1 − 1 3 ) = 4 \phi(12) = 12 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) = 4
ϕ ( 1 2 ) = 1 2 ⋅ ( 1 − 2 1 ) ⋅ ( 1 − 3 1 ) = 4
n n n ( gcd ( a , n ) = 1 ) a (\gcd(a, n) = 1) a ( g cd( a , n ) = 1 ) a
a ϕ ( n ) ≡ 1 m o d n a^{\phi(n)} \equiv 1 \bmod n
a ϕ ( n ) ≡ 1 m o d n
1 3 5 14 13^{5^{14}} 1 3 5 1 4
ϕ ( 19 ) = 18 \phi(19) = 18 ϕ ( 1 9 ) = 1 8 1 3 18 ≡ 1 m o d 19 13^{18} \equiv 1 \bmod 19 1 3 1 8 ≡ 1 m o d 1 9
指数部分が18の倍数であれば19を法として1と合同であるので, 指数部分が18の倍数のときは無視できる
ϕ ( 18 ) = 6 \phi(18) = 6 ϕ ( 1 8 ) = 6
5 6 ≡ 1 m o d 18 5^6 \equiv 1 \bmod 18
5 6 ≡ 1 m o d 1 8
したがって，
5 14 ≡ 5 6 ⋅ 2 ⋅ 5 2 ≡ 5 2 ≡ 7 m o d 18 5^{14} \equiv 5^{6 \cdot 2} \cdot 5^2 \equiv 5^2 \equiv 7 \bmod 18
5 1 4 ≡ 5 6 ⋅ 2 ⋅ 5 2 ≡ 5 2 ≡ 7 m o d 1 8
1 3 2 ≡ − 2 m o d 19 13^2 \equiv -2 \bmod 19 1 3 2 ≡ − 2 m o d 1 9
1 3 5 14 ≡ 1 3 7 ≡ 1 3 2 + 2 + 2 + 1 ≡ 1 3 2 ⋅ 1 3 2 ⋅ 1 3 2 ⋅ 1 3 1 ≡ ( − 2 ) ( − 2 ) ( − 2 ) ⋅ 13 ≡ − 104 ≡ 10 m o d 19 13^{5^{14}} \equiv 13^7 \equiv 13^{2+2+2+1} \equiv 13^2 \cdot 13^2 \cdot 13^2 \cdot 13^1 \equiv (-2)(-2)(-2)\cdot 13 \equiv -104 \equiv 10 \bmod 19 1 3 5 1 4 ≡ 1 3 7 ≡ 1 3 2 + 2 + 2 + 1 ≡ 1 3 2 ⋅ 1 3 2 ⋅ 1 3 2 ⋅ 1 3 1 ≡ ( − 2 ) ( − 2 ) ( − 2 ) ⋅ 1 3 ≡ − 1 0 4 ≡ 1 0 m o d 1 9
複数の素数p 1 , p 2 , ⋯ , p r p_1, p_2, \cdots, p_r p 1 , p 2 , ⋯ , p r a i ∈ Z p i a_i \in \mathbb{Z}_{p_i} a i ∈ Z p i i = 1 , ⋯ , r i = 1, \cdots, r i = 1 , ⋯ , r x ≡ a i m o d p i x \equiv a_i \bmod p_i x ≡ a i m o d p i x , 0 ≤ x ≤ M = p 1 p 2 ⋯ p r x, 0 \leq x \leq M = p_1p_2 \cdots p_r x , 0 ≤ x ≤ M = p 1 p 2 ⋯ p r
例：中国人剰余定理
連立合同式
{ x ≡ 2 m o d 3 x ≡ 3 m o d 5 x ≡ 2 m o d 7 \begin{aligned}
\begin{cases}
x \equiv 2 \bmod 3
\\
x \equiv 3 \bmod 5
\\
x \equiv 2 \bmod 7
\end{cases}
\end{aligned}
⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x ≡ 2 m o d 3 x ≡ 3 m o d 5 x ≡ 2 m o d 7
M = 3 × 5 × 7 = 105 M = 3 \times 5 \times 7 = 105 M = 3 × 5 × 7 = 1 0 5 M 1 = 5 × 7 = 35 , M 2 = 3 × 7 = 21 , M 3 = 3 × 5 = 15 M_1 = 5 \times 7 = 35, M_2 = 3 \times 7 = 21, M_3 = 3 \times 5 = 15 M 1 = 5 × 7 = 3 5 , M 2 = 3 × 7 = 2 1 , M 3 = 3 × 5 = 1 5
y 1 = 3 5 − 1 m o d 3 = 2 ( 35 × x ≡ 1 m o d 3 ) y 2 = 2 1 − 1 m o d 5 = 1 ( 21 × x ≡ 1 m o d 5 ) y 3 = 1 5 − 1 m o d 7 = 1 ( 15 × x ≡ 1 m o d 7 ) \begin{aligned}
y_1 = 35^{-1} \bmod 3 = 2 \quad (35 \times x \equiv 1 \bmod 3)
\\
y_2 = 21^{-1} \bmod 5 = 1 \quad (21 \times x \equiv 1 \bmod 5)
\\
y_3 = 15^{-1} \bmod 7 = 1 \quad (15 \times x \equiv 1 \bmod 7)
\end{aligned}
y 1 = 3 5 − 1 m o d 3 = 2 ( 3 5 × x ≡ 1 m o d 3 ) y 2 = 2 1 − 1 m o d 5 = 1 ( 2 1 × x ≡ 1 m o d 5 ) y 3 = 1 5 − 1 m o d 7 = 1 ( 1 5 × x ≡ 1 m o d 7 )
x = 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 2 ⋅ 15 ⋅ 1 = 140 + 63 + 30 = 233 m o d 105 = 23 x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \bmod 105 = 23 x = 2 ⋅ 3 5 ⋅ 2 + 3 ⋅ 2 1 ⋅ 1 + 2 ⋅ 1 5 ⋅ 1 = 1 4 0 + 6 3 + 3 0 = 2 3 3 m o d 1 0 5 = 2 3
以下の連立合同式を満たす整数x x x
{ x ≡ 3 m o d 11 x ≡ 1 m o d 13 x ≡ 7 m o d 17 \begin{aligned}
\begin{cases}
x \equiv 3 \bmod 11
\\
x \equiv 1 \bmod 13
\\
x \equiv 7 \bmod 17
\end{cases}
\end{aligned}
⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ x ≡ 3 m o d 1 1 x ≡ 1 m o d 1 3 x ≡ 7 m o d 1 7
M = 11 × 13 × 17 = 2431 M = 11 \times 13 \times 17 = 2431 M = 1 1 × 1 3 × 1 7 = 2 4 3 1 M 1 = 13 × 17 = 221 , M 2 = 11 × 17 = 187 , M 3 = 11 × 13 = 143 M_1 = 13 \times 17 = 221, M_2 = 11 \times 17 = 187, M_3 = 11 \times 13 = 143 M 1 = 1 3 × 1 7 = 2 2 1 , M 2 = 1 1 × 1 7 = 1 8 7 , M 3 = 1 1 × 1 3 = 1 4 3
y 1 = 22 1 − 1 m o d 11 = 1 ( 221 × x ≡ 1 m o d 11 ) y 2 = 18 7 − 1 m o d 13 = 8 ( 187 × x ≡ 1 m o d 13 ) y 3 = 14 3 − 1 m o d 17 = 5 ( 143 × x ≡ 1 m o d 17 ) \begin{aligned}
y_1 = 221^{-1} \bmod 11 = 1 \quad (221 \times x \equiv 1 \bmod 11)
\\
y_2 = 187^{-1} \bmod 13 = 8 \quad (187 \times x \equiv 1 \bmod 13)
\\
y_3 = 143^{-1} \bmod 17 = 5 \quad (143 \times x \equiv 1 \bmod 17)
\end{aligned}
y 1 = 2 2 1 − 1 m o d 1 1 = 1 ( 2 2 1 × x ≡ 1 m o d 1 1 ) y 2 = 1 8 7 − 1 m o d 1 3 = 8 ( 1 8 7 × x ≡ 1 m o d 1 3 ) y 3 = 1 4 3 − 1 m o d 1 7 = 5 ( 1 4 3 × x ≡ 1 m o d 1 7 )
x = 3 ⋅ 221 ⋅ 1 + 1 ⋅ 187 ⋅ 8 + 7 ⋅ 143 ⋅ 5 = 7164 m o d 2431 = 2302 x = 3 \cdot 221 \cdot 1 + 1 \cdot 187 \cdot 8 + 7 \cdot 143 \cdot 5 = 7164 \bmod 2431 = 2302 x = 3 ⋅ 2 2 1 ⋅ 1 + 1 ⋅ 1 8 7 ⋅ 8 + 7 ⋅ 1 4 3 ⋅ 5 = 7 1 6 4 m o d 2 4 3 1 = 2 3 0 2
1977年にMITにいたRivest, Shamir, Adlemanによって開発された素因数分解の困難性を利用した公開鍵暗号方式
鍵生成
利用者は2つの大きな素数 p , q p, q p , q ∣ p ∣ ≃ ∣ q ∣ |p| \simeq |q| ∣ p ∣ ≃ ∣ q ∣
n = p q , ϕ ( n ) = ( p − 1 ) ( q − 1 ) n = pq, \phi(n) = (p - 1)(q - 1) n = p q , ϕ ( n ) = ( p − 1 ) ( q − 1 ) e ∈ Z ϕ ( n ) s . t gcd ( ϕ ( n ) , e ) = 1 e \in \mathbb{Z}_{\phi(n)} \quad s.t \quad \gcd(\phi(n), e) = 1 e ∈ Z ϕ ( n ) s . t g cd( ϕ ( n ) , e ) = 1 d = e − 1 m o d ϕ ( n ) d = e^{-1} \bmod \phi(n) d = e − 1 m o d ϕ ( n ) e d ≡ 1 m o d ϕ ( n ) ed \equiv 1 \bmod \phi(n) e d ≡ 1 m o d ϕ ( n )
秘密鍵: 復号鍵 d , ( p , q ) d, (p, q) d , ( p , q ) e , n e, n e , n
平文
m ∈ Z n m \in \mathbb{Z}_n m ∈ Z n
暗号化
c = e ( m ) : = m e m o d n c = e(m) := m^e \bmod n c = e ( m ) : = m e m o d n
復号
m = d ( c ) : = c d m o d n m = d(c) := c^{d} \bmod n m = d ( c ) : = c d m o d n
定理： 任意の平文m ∈ Z n m \in \mathbb{Z}_n m ∈ Z n d ( e ( m ) ) = m e d m o d n = m d(e(m)) = m^{ed} \bmod n = m d ( e ( m ) ) = m e d m o d n = m
例題:
图中有错误， d = 34 9 − 1 m o d 840 = 349 , c = 12 3 349 m o d 899 = 402 d = 349^{-1} \bmod 840 = 349, c = 123^{349} \bmod 899 = 402 d = 3 4 9 − 1 m o d 8 4 0 = 3 4 9 , c = 1 2 3 3 4 9 m o d 8 9 9 = 4 0 2
d ≡ e − 1 m o d ϕ ( n ) d \equiv e^{-1} \bmod \phi(n) d ≡ e − 1 m o d ϕ ( n ) e d ≡ 1 m o d ϕ ( n ) ed \equiv 1 \bmod \phi(n) e d ≡ 1 m o d ϕ ( n ) e ∈ Z ϕ ( n ) e \in \mathbb{Z}_{\phi(n)} e ∈ Z ϕ ( n )
拡張ユークリッド互除法
入力: u , v ( u > v ) u, v (u > v) u , v ( u > v )
出力: gcd ( u , v ) \gcd(u, v) g cd( u , v ) s , t s, t s , t s . t s u + t v = gcd ( u , v ) \quad s.t \quad su + tv = \gcd(u, v) s . t s u + t v = g cd( u , v )
( u , v ) = ( ϕ ( n ) , e ) (u, v) = (\phi(n), e) ( u , v ) = ( ϕ ( n ) , e )
結果:
gcd ( u , v ) = gcd ( ϕ ( n ) , e ) = 1 , s ϕ ( n ) + t e = 1 \gcd(u, v) = \gcd(\phi(n), e) = 1, \quad s\phi(n) + te = 1
g cd( u , v ) = g cd( ϕ ( n ) , e ) = 1 , s ϕ ( n ) + t e = 1
ゆえに, t e ≡ 1 m o d ϕ ( n ) te \equiv 1 \bmod \phi(n) t e ≡ 1 m o d ϕ ( n )
従って, e − 1 e^{-1} e − 1 t t t
入力: u , v ( u > v ) u, v (u > v) u , v ( u > v )
出力: gcd ( u , v ) \gcd(u, v) g cd( u , v ) s , t s, t s , t s . t s u + t v = gcd ( u , v ) \quad s.t \quad su + tv = \gcd(u, v) s . t s u + t v = g cd( u , v )
計算例：拡張ユークリッド法による秘密鍵の計算
例題:
共通の法 n n n
法 n n n e , d e, d e , d n n n
同報通信, 同一平文：
同一の平文を複数の送信元へ暗号化して送信, 同一の公開鍵 e e e
{ c 1 ≡ m e m o d n 1 ⋮ c L ≡ m e m o d n L \begin{aligned}
\begin{cases}
c_1 \equiv &m^e \bmod n_1
\\
&\vdots
\\
c_L \equiv &m^e \bmod n_L
\end{cases}
\end{aligned}
⎩ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎧ c 1 ≡ c L ≡ m e m o d n 1 ⋮ m e m o d n L
小さな平文 m m m
m m m n n n e e e m o d \bmod m o d
N N N N / log 2 N N / \log_2 N N / log 2 N p , q p, q p , q
p − 1 , q + 1 p - 1, q + 1 p − 1 , q + 1 r r r r r r p , q p, q p , q
一方向性 ：満たす(と考えられている)強秘匿性 ：満たさない
ヤコビ記号が1か-1かを判定可能、平文に関する情報が漏れる可能性がある
識別不可能性 ：満たさない
平文 m 1 , m 2 m_1, m_2 m 1 , m 2 m 1 e m o d n , m 2 e m o d n m_1^e \bmod n, m_2^e \bmod n m 1 e m o d n , m 2 e m o d n e , n e, n e , n
頑健性 ：満たさない
暗号文c A = m A e m o d n c_A = m_A^e \bmod n c A = m A e m o d n e , n e, n e , n c E = m E e m o d n c_E = m_E^e \bmod n c E = m E e m o d n c A c_A c A c A c E ≡ ( m A m E ) e m o d n c_Ac_E \equiv (m_Am_E)^e \bmod n c A c E ≡ ( m A m E ) e m o d n m A m E m_Am_E m A m E
IND-CCA2を満たすようにRSA暗号を改良同一の平文に対して、同一の暗号文が出力されないように乱数を用いる
二つの素数 p = 31 , q = 37 p = 31, q = 37 p = 3 1 , q = 3 7
(1) 公開鍵 e = 271 e = 271 e = 2 7 1 d d d
n = p q = 1147 n = pq = 1147 n = p q = 1 1 4 7 ϕ ( n ) = ( p − 1 ) ( q − 1 ) = 1080 \phi(n) = (p - 1)(q - 1) = 1080 ϕ ( n ) = ( p − 1 ) ( q − 1 ) = 1 0 8 0 d = e − 1 m o d ϕ ( n ) = 27 1 − 1 m o d 1080 = 271 d = e^{-1} \bmod \phi(n) = 271^{-1} \bmod 1080 = 271 d = e − 1 m o d ϕ ( n ) = 2 7 1 − 1 m o d 1 0 8 0 = 2 7 1
(2) 平文 m = 333 m = 333 m = 3 3 3
暗号化: c = m e m o d n = 33 3 271 m o d 1147 = 33 3 256 × 33 3 8 × 33 3 4 × 33 3 2 × 333 m o d 1147 = 333 c = m^e \bmod n = 333^{271} \bmod 1147 = 333^{256} \times 333^8 \times 333^4 \times 333^2 \times 333 \bmod 1147 = 333 c = m e m o d n = 3 3 3 2 7 1 m o d 1 1 4 7 = 3 3 3 2 5 6 × 3 3 3 8 × 3 3 3 4 × 3 3 3 2 × 3 3 3 m o d 1 1 4 7 = 3 3 3
復号: c d m o d n = 33 3 271 m o d 1147 = 333 c^d \bmod n = 333^{271} \bmod 1147 = 333 c d m o d n = 3 3 3 2 7 1 m o d 1 1 4 7 = 3 3 3
1982年にElGamalによって開発された離散対数問題の困難性を利用した公開鍵暗号方式
鍵生成
利用者は大きな素数p p p
乗法群Z p ∗ \mathbb{Z}^*_p Z p ∗ α \alpha α
x ∈ Z p − 1 x \in \mathbb{Z}_{p-1} x ∈ Z p − 1 y = α x m o d p y = \alpha^x \bmod p y = α x m o d p
秘密鍵: 復号鍵 x x x y , p , α y, p, \alpha y , p , α
平文
m ∈ Z n m \in \mathbb{Z}_n m ∈ Z n
暗号化
c = ( c 1 , c 2 ) : = ( α r m o d p , m y r m o d p ) c = (c_1, c_2) := (\alpha^r \bmod p, my^r \bmod p) c = ( c 1 , c 2 ) : = ( α r m o d p , m y r m o d p ) r ∈ Z p − 1 : \quad \color{red}{r \in \mathbb{Z}_{p-1}}: r ∈ Z p − 1 :
復号
m = c 2 / c 1 x m o d p m = c_2 / c_1^x \bmod p m = c 2 / c 1 x m o d p
F p = Z p = Z / ( p Z ) \mathbb{F}_p = \mathbb{Z}_p = \mathbb{Z} / (p\mathbb{Z}) F p = Z p = Z / ( p Z ) F p ∗ = F p \mathbb{F}^*_p = \mathbb{F}_p F p ∗ = F p { 0 } \lbrace 0 \rbrace { 0 }
α i ≠ 1 , i = 1 , ⋯ , p − 2 , α p − 1 = 1 \alpha^i \neq 1, i = 1, \cdots, p-2, \quad \alpha^{p-1} = 1
α i = 1 , i = 1 , ⋯ , p − 2 , α p − 1 = 1
を満たすα ∈ F p ∗ \alpha \in \mathbb{F}^*_p α ∈ F p ∗ F p \mathbb{F}_p F p 原始元 という.
このとき, 以下の巡回群のように表せる.
F p ∗ = { α 0 ( = 1 ) , α 1 , ⋯ , α p − 2 } \mathbb{F}^*_p = \lbrace \alpha^0(=1), \alpha^1, \cdots, \alpha_{p-2} \rbrace
F p ∗ = { α 0 ( = 1 ) , α 1 , ⋯ , α p − 2 }
定理： 任意の平文m ∈ Z p m \in \mathbb{Z}_p m ∈ Z p d ( e ( m ) ) = m d(e(m)) = m d ( e ( m ) ) = m
例題:
平文毎で共通の乱数r r r r r r
c 1 = ( α r , m 1 y r ) , c 2 = ( α r , m 2 y r ) c_1 = (\alpha^r, m_1y^r), c_2 = (\alpha^r, m_2y^r) c 1 = ( α r , m 1 y r ) , c 2 = ( α r , m 2 y r )
c 2 c 1 = m 1 y r m 2 y r = m 1 m 2 m o d p \frac{c_2}{c_1} = \frac{m_1y^r}{m_2y^r} = \frac{m_1}{m_2} \bmod p
c 1 c 2 = m 2 y r m 1 y r = m 2 m 1 m o d p
となり, m 1 m_1 m 1 m 2 m_2 m 2
p − 1 p - 1 p − 1 q q q q q q
Pohlig-Hellmanのアルゴリズムに対する安全性を考慮
p p p
512ビット以上(1980年代)
1024ビット以上(1996年)
20484ビット以上(現在以降)
が推奨されている
一方向性 ： 満たす強秘匿性 ： 満たす識別不可能性 ： 満たす
確率暗号 : 乱数 r r r 確定暗号 : 同じ平文を暗号化すると暗号文が同じになる暗号. 例. RSA暗号, Rabin暗号
頑健性 ： 満たさない
暗号文c = ( c 1 , c 2 ) = ( α r , m y r ) c = (c_1, c_2) = (\alpha^r, my^r) c = ( c 1 , c 2 ) = ( α r , m y r ) m 0 < p m_0 < p m 0 < p c ′ = ( c 1 , m 0 c 2 ) c^{'} = (c_1, m_0c_2) c ′ = ( c 1 , m 0 c 2 ) c ′ = ( α r , m 0 m y r ) m o d p c^{'} = (\alpha^r, m_0my^r) \bmod p c ′ = ( α r , m 0 m y r ) m o d p m 0 m m_0m m 0 m
ElGamal暗号の改良版
鍵生成
利用者は大きな素数p p p
位数p p p G \mathbb{G} G α , β ) ∈ G 2 \alpha, \beta) \in \mathbb{G}^2 α , β ) ∈ G 2
( x 00 , x 01 , x 10 , x 11 , x 20 , x 21 ) ∈ G 6 (x_{00}, x_{01}, x_{10}, x_{11}, x_{20}, x_{21}) \in \mathbb{G}^6 ( x 0 0 , x 0 1 , x 1 0 , x 1 1 , x 2 0 , x 2 1 ) ∈ G 6 y i = α x i 0 β x i 1 , i = 0 , 1 , 2 y_i = \alpha^{x_{i0}} \beta^{x_{i1}}, i = 0, 1, 2 y i = α x i 0 β x i 1 , i = 0 , 1 , 2 H H H
秘密鍵: 復号鍵 ( x 00 , x 01 , x 10 , x 11 , x 20 , x 21 ) (x_{00}, x_{01}, x_{10}, x_{11}, x_{20}, x_{21}) ( x 0 0 , x 0 1 , x 1 0 , x 1 1 , x 2 0 , x 2 1 ) y 0 , y 1 , y 2 , G , α , β , H y_0, y_1, y_2, \mathbb{G}, \alpha, \beta, H y 0 , y 1 , y 2 , G , α , β , H
平文
m ∈ Z n m \in \mathbb{Z}_n m ∈ Z n
暗号化
c = ( c 1 , c 2 , c 3 , c 4 ) : = ( α r , β r , m y 0 r , ( y 1 y 2 H ( c 1 . c 2 , c 3 ) ) r ) m o d p c = (c_1, c_2, c_3, c_4) := (\alpha^r, \beta^r, my_0^r, (y_1y_2^{H(c_1. c_2, c_3)})^r) \bmod p c = ( c 1 , c 2 , c 3 , c 4 ) : = ( α r , β r , m y 0 r , ( y 1 y 2 H ( c 1 . c 2 , c 3 ) ) r ) m o d p r ∈ Z p : \quad \color{red}{r \in \mathbb{Z}_p}: r ∈ Z p :
復号
c 4 = ( c 1 x 10 , c 2 x 10 ) ( y 1 y 2 H ( c 1 , c 2 , c 3 ) ) m o d p c_4 = (c_1^{x_{10}}, c_2^{x_{10}})(y_1 y_2^{H(c_1, c^2, c^3)}) \bmod p c 4 = ( c 1 x 1 0 , c 2 x 1 0 ) ( y 1 y 2 H ( c 1 , c 2 , c 3 ) ) m o d p m = c 3 ⋅ c 1 − x 00 c 2 − x 01 m = c_3 \cdot c_1^{-x_{00}} c_2^{-x_{01}} m = c 3 ⋅ c 1 − x 0 0 c 2 − x 0 1
関数h : { 0 , 1 } n ⇒ { 0 , 1 } m ( n ≥ m ) h: \lbrace 0, 1 \rbrace^n \Rightarrow \lbrace 0, 1 \rbrace^m (n \geq m) h : { 0 , 1 } n ⇒ { 0 , 1 } m ( n ≥ m )
x ∈ { 0 , 1 } n x \in \lbrace 0, 1 \rbrace^n x ∈ { 0 , 1 } n h ( x ) h(x) h ( x )
x , y ∈ { 0 , 1 } n s . t . x ≠ y x, y \in \lbrace 0, 1 \rbrace^n \quad s.t. x \neq y x , y ∈ { 0 , 1 } n s . t . x = y h ( x ) = h ( y ) h(x) = h(y) h ( x ) = h ( y ) ( x , y ) (x, y) ( x , y ) 衝突困難性 )
素数p = 61 p = 61 p = 6 1 x = 33 x = 33 x = 3 3
(1) 原始元α ∈ Z p \alpha \in \mathbb{Z}_p α ∈ Z p
1 2 3 4 5 6 7 8 9 10 p = 61 alpha = 2 def main (): for i in range (1 , p): primitive = alpha ** i % p print ("i = %d, primitive-element = %d" % (i, primitive)) if __name__ == "__main__" : main()
ソースコードを実行すると、素数p = 61 p = 61 p = 6 1 α = 2 \alpha = 2 α = 2
(2) 公開鍵y y y α \alpha α
y = α x m o d p ≡ 2 33 m o d 61 ≡ 53 y = \alpha^x \bmod p \equiv 2^{33} \bmod 61 \equiv 53 y = α x m o d p ≡ 2 3 3 m o d 6 1 ≡ 5 3
(3) 平文m = 41 m = 41 m = 4 1 r = 27 r = 27 r = 2 7
暗号化:
y = α x m o d p = 53 y = \alpha^x \bmod p = 53 y = α x m o d p = 5 3 c 1 = α r m o d p = 2 27 m o d 61 = 38 c_1 = \alpha^r \bmod p = 2^{27} \bmod 61 = 38 c 1 = α r m o d p = 2 2 7 m o d 6 1 = 3 8 c 2 = m ⋅ y r m o d p = 41 ⋅ 5 3 27 m o d 61 = 50 c_2 = m \cdot y^r \bmod p = 41 \cdot 53^{27} \bmod 61 = 50 c 2 = m ⋅ y r m o d p = 4 1 ⋅ 5 3 2 7 m o d 6 1 = 5 0
復号:
m = c 2 / c 1 x m o d p = 50 / 3 8 33 m o d 61 = 41 m = c_2 / c_1^x \bmod p = 50 / 38^{33} \bmod 61 = 41 m = c 2 / c 1 x m o d p = 5 0 / 3 8 3 3 m o d 6 1 = 4 1
1978年に提唱された公開鍵暗号方式であり、一般の線形符号の復号問題の困難性(NP完全)を利用する
鍵生成
C : F q C: \mathbb{F}_q C : F q ( n , k ) (n, k) ( n , k ) G : k × n G: k \times n G : k × n r a n k G = k rank G = k r a n k G = k
C : = { c = x G ∣ x ∈ F q k } , d : = min { d H ( c 1 , c 2 ) ∣ c 1 , c 2 ∈ C } C := \lbrace c = xG \ |\ x \in \mathbb{F}_q^k \rbrace, \quad d := \min \lbrace d_H(c_1, c_2) \ |\ c_1, c_2 \in C \rbrace C : = { c = x G ∣ x ∈ F q k } , d : = min { d H ( c 1 , c 2 ) ∣ c 1 , c 2 ∈ C }
S : F q S: \mathbb{F}_q S : F q k × k k \times k k × k P : F q P: \mathbb{F}_q P : F q n × n n \times n n × n
秘密鍵: S , G , P S, G, P S , G , P G ′ : = S G P G^{'} := SGP G ′ : = S G P
平文
m ∈ F q k m \in \mathbb{F}_q^k m ∈ F q k
暗号化
c : = m G ′ + e ∈ F q n c := mG^{'} + e \in \mathbb{F}_q^n c : = m G ′ + e ∈ F q n e ∈ F q n ( w t ( e ) ≤ t : = ⌊ d − 1 2 ⌋ ) e \in \mathbb{F}_q^n(wt(e) \leq t := \lfloor \frac{d-1}{2} \rfloor) e ∈ F q n ( w t ( e ) ≤ t : = ⌊ 2 d − 1 ⌋ )
復号
y : = c P − 1 ( = m S G + e P − 1 ) y := cP^{-1}(= mSG + eP^{-1}) y : = c P − 1 ( = m S G + e P − 1 ) y y y c ′ = m ′ G ∈ C c^{'} = m^{'}G \in C c ′ = m ′ G ∈ C m ′ = m S m^{'} = mS m ′ = m S m = m ′ S − 1 m = m^{'}S^{-1} m = m ′ S − 1
1978年にRabinにより提案された公開鍵暗号方式
鍵生成
2つの素数p , q ( ∣ p ∣ ≃ ∣ q ∣ , p ≡ q ≡ 3 m o d 4 ) p, q (|p| \simeq |q|, p \equiv q \equiv 3 \bmod 4) p , q ( ∣ p ∣ ≃ ∣ q ∣ , p ≡ q ≡ 3 m o d 4 )
Blum数n = p q n = pq n = p q
λ ( n ) = l c m ( p − 1 , q − 1 ) \lambda(n) = lcm(p - 1, q - 1) λ ( n ) = l c m ( p − 1 , q − 1 ) λ ( n ) \lambda(n) λ ( n ) e ∈ Z λ ( n ) e \in \mathbb{Z}_{\lambda(n)} e ∈ Z λ ( n ) e d ≡ 1 m o d λ ( n ) ed \equiv 1 \bmod \lambda(n) e d ≡ 1 m o d λ ( n ) d d d
秘密鍵: d , p , q d, p, q d , p , q e , n e, n e , n
平文
m ∈ Z n , 0 < m < n 2 , ( m n ) = 1 m \in \mathbb{Z}_n, 0 < m < \frac{n}{2}, (\frac{m}{n}) = 1 m ∈ Z n , 0 < m < 2 n , ( n m ) = 1
暗号化
c : = m 2 m o d n c := m^2 \bmod n c : = m 2 m o d n
復号
m p = c ( p + 1 ) / 4 m o d p , m q = c ( p + 1 ) / 4 m o d q m_p = c^{(p + 1)/4} \bmod p, m_q = c^{(p + 1)/4} \bmod q m p = c ( p + 1 ) / 4 m o d p , m q = c ( p + 1 ) / 4 m o d q ( a , b ) ∈ { ( m p , m q ) , ( − m p , m q ) , ( m p , − m q ) , ( − m p − m q ) } (a, b) \in \lbrace (m_p, m_q), (-m_p, m_q), (m_p, -m_q), (-m_p -m_q) \rbrace ( a , b ) ∈ { ( m p , m q ) , ( − m p , m q ) , ( m p , − m q ) , ( − m p − m q ) } m ≡ a m o d p , m ≡ b m o d q m \equiv a \bmod p, m \equiv b \bmod q m ≡ a m o d p , m ≡ b m o d q m m m m m m 0 < n < n 2 , ( m n ) = 1 0 < n <\frac{n}{2}, (\frac{m}{n}) = 1 0 < n < 2 n , ( n m ) = 1
x ∈ Z n ∗ x \in \mathbb{Z}_n^* x ∈ Z n ∗ a = x 2 m o d n a = x^2 \bmod n a = x 2 m o d n a ∈ Z n ∗ a \in \mathbb{Z}_n^* a ∈ Z n ∗ Q R n ⊂ Z n ∗ QR_n \subset \mathbb{Z}_n^* Q R n ⊂ Z n ∗ a ∈ Z n ∗ a \in \mathbb{Z}_n^* a ∈ Z n ∗ n n n 平方剰余 という.
また、平方剰余でない要素の集合をQ N R n = Z n ∗ QNR_n = \mathbb{Z}_n^* Q N R n = Z n ∗ Q R n QR_n Q R n n n n 平方非剰余 という.
法が素数の場合の平方剰余
α \alpha α Z p ∗ \mathbb{Z}_p^* Z p ∗ α ∈ Z p ∗ \alpha \in \mathbb{Z}_p^* α ∈ Z p ∗ a = α i m o d p a = \alpha^i \bmod p a = α i m o d p
i i i a a a i i i a a a
a p − 1 2 ≡ { 1 m o d p , a ∈ Q R n − 1 m o d p , a ∈ Q N R n \begin{aligned}
a^{\frac{p-1}{2}} \equiv \begin{cases}
1 \bmod p, \quad a \in QR_n
\\
-1 \bmod p, \quad a \in QNR_n
\end{cases}
\end{aligned}
a 2 p − 1 ≡ { 1 m o d p , a ∈ Q R n − 1 m o d p , a ∈ Q N R n
p p p a ∈ Z p ∗ a \in \mathbb{Z}_p^* a ∈ Z p ∗ ルジャンドル記号 を以下で定義する.
( a p ) : = { 1 , a ∈ Q R p − 1 , a ∈ Q N R p ( a p ) ≡ a p − 1 2 m o d p \begin{aligned}
(\frac{a}{p}) := \begin{cases}
1, \quad a \in QR_p
\\
-1, \quad a \in QNR_p
\end{cases} \qquad (\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \bmod p
\end{aligned}
( p a ) : = { 1 , a ∈ Q R p − 1 , a ∈ Q N R p ( p a ) ≡ a 2 p − 1 m o d p
n = p 1 e 1 p 2 e 2 ⋯ p r e r n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} n = p 1 e 1 p 2 e 2 ⋯ p r e r a ∈ Z p ∗ a \in \mathbb{Z}_p^* a ∈ Z p ∗ ヤコビ記号 を以下で定義する.
( a n ) : = ( a p 1 ) e 1 ( a p 2 ) e 2 ⋯ ( a p r ) e r \begin{aligned}
(\frac{a}{n}) := (\frac{a}{p_1})^{e_1} (\frac{a}{p_2})^{e_2} \cdots (\frac{a}{p_r})^{e_r}
\end{aligned}
( n a ) : = ( p 1 a ) e 1 ( p 2 a ) e 2 ⋯ ( p r a ) e r
a ∈ Q R n a \in QR_n a ∈ Q R n a a a
法が合成数の場合の平方剰余:
n = p q n = pq n = p q a ∈ Q R n a \in QR_n a ∈ Q R n x 2 ≡ a m o d n x^2 \equiv a \bmod n x 2 ≡ a m o d n x 2 ≡ a m o d p x^2 \equiv a \bmod p x 2 ≡ a m o d p x p x_p x p x 2 ≡ a m o d q x^2 \equiv a \bmod q x 2 ≡ a m o d q x p x_p x p x p , x q x_p, x_q x p , x q x p , x q x_p, x_q x p , x q
例題:
素数判定アルゴリズムを用いて, n 1 = 53 , n 2 = 55 n_1 = 53, n_2 = 55 n 1 = 5 3 , n 2 = 5 5 L = 3 L = 3 L = 3 1 64 \frac{1}{64} 6 4 1
共通鍵暗号方式を利用する際には, 安全な通信路を用いて , 暗号化・復号鍵を共有しなければならない.
安全な通信路を用意するのは手間がかかるため, 安全ではない通信路を利用して , 通信相手に鍵を送ったり（鍵配送 ）, 共有したり(鍵共有 )するための方法があると有益である.
1つの解決法として, 公開鍵暗号方式を利用する方法がある. 共有したい鍵を公開鍵暗号方式で送る方法が考えられる. (公開鍵暗号方式は計算量が大きいので, 鍵の共有のみに利用して, 共有後は高速に動作する共通鍵暗号方式を利用)
1976年に提案された方式であり, 離散対数問題 に基づく初めての方式であり, 注目を集めた
例：DH鍵配送方式
離散対数問題を解くことが困難であること
p − 1 p - 1 p − 1 p p p p p p
1980年頃 512ビット, 1996年頃 1024ビット推奨
通信相手を確認することができないため, 通信路の間に入るとなりすますことが可能
ユーザA A A ( P A , S A ) (P_A, S_A) ( P A , S A ) P A P_A P A B B B
ユーザB B B K K K b = E P A ( K ) b = E_{P_A}(K) b = E P A ( K ) A A A
ユーザA A A K = D S A ( b ) K = D_{S_A}(b) K = D S A ( b )
問題点: DH鍵配送方式と同様に中間攻撃(なりすまし)の可能性がある
事前通信が不要 な方式
Kerberos
鍵配送センター KDC (Key Distribution Center)(利用者 U ∈ { A , B , ⋯ } U \in \lbrace A, B, \cdots \rbrace U ∈ { A , B , ⋯ } S U S_U S U
Diffie-Hellman公開鍵配送方式において, 3人で鍵を共有する場合の方法についてまとめよ. また, 具体的な数値例を示せ.
まず、準備として、素数 p p p Z p ∗ \mathbb{Z}_p^* Z p ∗ g g g ( p , g ) (p, g) ( p , g )
ユーザーアリス：x ∈ Z p ∗ x \in \mathbb{Z}_p^* x ∈ Z p ∗ R 1 = g x m o d p R_1 = g^x \bmod p R 1 = g x m o d p
ユーザーイブ：z ∈ Z p ∗ z \in \mathbb{Z}_p^* z ∈ Z p ∗ R 2 = g z m o d p R_2 = g^z \bmod p R 2 = g z m o d p
ユーザーボブ：y ∈ Z p ∗ y \in \mathbb{Z}_p^* y ∈ Z p ∗ R 3 = g y m o d p R_3 = g^y \bmod p R 3 = g y m o d p
お互い送信後：
ユーザーアリス：K 1 = ( R 2 ) x m o d p K_1 = (R_2)^x \bmod p K 1 = ( R 2 ) x m o d p
ユーザーイブ：K 1 = ( R 1 ) z m o d p , K 2 = ( R 3 ) z m o d p K_1 = (R_1)^z \bmod p, K_2 = (R_3)^z \bmod p K 1 = ( R 1 ) z m o d p , K 2 = ( R 3 ) z m o d p
ユーザーボブ：K 2 = ( R 2 ) y m o d p K_2 = (R_2)^y \bmod p K 2 = ( R 2 ) y m o d p
確認：
アリスとイブの秘密鍵：K 1 = g x z m o d p K_1 = g^{xz} \bmod p K 1 = g x z m o d p
イブとボブの秘密鍵：K 2 = g z y m o d p K_2 = g^{zy} \bmod p K 2 = g z y m o d p
以下は具体的な数値例を示す
準備として、素数 p = 23 p = 23 p = 2 3 Z p ∗ \mathbb{Z}_p^* Z p ∗ g = 5 g = 5 g = 5 ( 23 , 5 ) (23, 5) ( 2 3 , 5 )
ユーザーアリス：7 ∈ Z p ∗ 7 \in \mathbb{Z}_p^* 7 ∈ Z p ∗ R 1 = 5 7 m o d 23 = 17 R_1 = 5^7 \bmod 23 = 17 R 1 = 5 7 m o d 2 3 = 1 7
ユーザーイブ：11 ∈ Z p ∗ 11 \in \mathbb{Z}_p^* 1 1 ∈ Z p ∗ R 2 = 5 11 m o d 23 = 22 R_2 = 5^{11} \bmod 23 = 22 R 2 = 5 1 1 m o d 2 3 = 2 2
ユーザーボブ：15 ∈ Z p ∗ 15 \in \mathbb{Z}_p^* 1 5 ∈ Z p ∗ R 3 = 5 15 m o d 23 = 19 R_3 = 5^{15} \bmod 23 = 19 R 3 = 5 1 5 m o d 2 3 = 1 9
お互い送信後：
ユーザーアリス：K 1 = ( 22 ) 7 m o d 23 = 22 K_1 = (22)^7 \bmod 23 = 22 K 1 = ( 2 2 ) 7 m o d 2 3 = 2 2
ユーザーイブ：K 1 = ( 17 ) 11 m o d 23 = 22 , K 2 = ( 19 ) 11 m o d 23 = 22 K_1 = (17)^{11} \bmod 23 = 22, K_2 = (19)^{11} \bmod 23 = 22 K 1 = ( 1 7 ) 1 1 m o d 2 3 = 2 2 , K 2 = ( 1 9 ) 1 1 m o d 2 3 = 2 2
ユーザーボブ：K 2 = ( 22 ) 15 m o d 23 = 22 K_2 = (22)^{15} \bmod 23 = 22 K 2 = ( 2 2 ) 1 5 m o d 2 3 = 2 2
確認：
アリスとイブの秘密鍵：K 1 = 5 7 ∗ 11 m o d 23 = 22 K_1 = 5^{7 * 11} \bmod 23 = 22 K 1 = 5 7 ∗ 1 1 m o d 2 3 = 2 2
イブとボブの秘密鍵：K 2 = 5 11 ∗ 15 m o d 23 = 22 K_2 = 5^{11 * 15} \bmod 23 = 22 K 2 = 5 1 1 ∗ 1 5 m o d 2 3 = 2 2
電子情報はコピーや改ざんが容易に可能
電子署名 : 電子的手段による署名（紙媒体でのサインや印鑑と同じ機能を持たせる）
ディジタル署名 ：公開鍵暗号を利用して実現される電子署名
暗号化 ： 暗号化（公開） ⇒ \Rightarrow ⇒ 署名 ： 署名（秘密） ⇒ \Rightarrow ⇒
鍵生成
2つの大きな素数 p , q ( ∣ p ∣ ≃ ∣ q ∣ ) p, q (|p| \simeq |q|) p , q ( ∣ p ∣ ≃ ∣ q ∣ )
n = p q , φ ( n ) = ( p − 1 ) ( q − 1 ) , ( λ ( n ) = l c m ( p − 1 , q − 1 ) ) n = pq, \varphi(n) = (p - 1)(q - 1), \quad (\lambda (n) = lcm(p - 1, q - 1)) n = p q , φ ( n ) = ( p − 1 ) ( q − 1 ) , ( λ ( n ) = l c m ( p − 1 , q − 1 ) ) e ∈ Z φ ( n ) e \in \mathbb{Z}_{\varphi (n)} e ∈ Z φ ( n ) gcd ( e , φ ( n ) ) = 1 \gcd(e, \varphi (n)) = 1 g cd( e , φ ( n ) ) = 1 d = e − 1 m o d φ ( n ) d = e^{-1} \bmod \varphi (n) d = e − 1 m o d φ ( n ) ( e d ≡ 1 m o d φ ( n ) ) (ed \equiv 1 \bmod \varphi (n)) ( e d ≡ 1 m o d φ ( n ) ) h : h: h :
秘密鍵(署名鍵 ): d , ( p , q ) d, (p, q) d , ( p , q ) 検証鍵 ): e , n e, n e , n
署名
s ≡ m d m o d p ( h ( m ) d m o d p ) s \equiv m^d \bmod p \quad (h(m)^d \bmod p) s ≡ m d m o d p ( h ( m ) d m o d p )
検証
v ≡ s e m o d p v \equiv s^e \bmod p v ≡ s e m o d p v = m ( v = h ( m ) ) v = m \quad (v = h(m)) v = m ( v = h ( m ) )
s ( m 1 ) s(m_1) s ( m 1 ) m 1 m_1 m 1 s ( m 2 ) s(m_2) s ( m 2 ) m 2 m_2 m 2
s ( m 1 ⋅ m 2 ) ≡ ( m 1 ⋅ m 2 ) d m o d n ≡ m 1 d ⋅ m 2 d m o d n ≡ ( m 1 m o d n ) ⋅ ( m 2 m o d n ) ≡ s ( m 1 ) ⋅ s ( m 2 ) \begin{aligned}
s(m_1 \cdot m_2) &\equiv (m_1 \cdot m_2)^d \bmod n \equiv m_1^d \cdot m_2^d \bmod n
\\
&\equiv (m_1 \bmod n) \cdot (m_2 \bmod n) \equiv s(m_1) \cdot s(m_2)
\end{aligned}
s ( m 1 ⋅ m 2 ) ≡ ( m 1 ⋅ m 2 ) d m o d n ≡ m 1 d ⋅ m 2 d m o d n ≡ ( m 1 m o d n ) ⋅ ( m 2 m o d n ) ≡ s ( m 1 ) ⋅ s ( m 2 )
攻撃:
文書 m m m s ( m ) s(m) s ( m ) s ( m ) − 1 m o d n s(m)^{-1} \bmod n s ( m ) − 1 m o d n
y = x ⋅ m m o d n y = x \cdot m \bmod n y = x ⋅ m m o d n 偽造署名 s ( x ) = s ( y ) ⋅ s ( m ) − 1 m o d n = s ( x ) ⋅ s ( m ) ⋅ s ( m ) − 1 m o d n s(x) = s(y) \cdot s(m)^{-1} \bmod n = s(x) \cdot s(m) \cdot s(m)^{-1} \bmod n s ( x ) = s ( y ) ⋅ s ( m ) − 1 m o d n = s ( x ) ⋅ s ( m ) ⋅ s ( m ) − 1 m o d n
1996年 Bellare, Rogaway
鍵生成
素数 p , Z p ∗ p, \mathbb{Z}_p^* p , Z p ∗ α \alpha α
x ∈ Z p − 1 x \in \mathbb{Z}^{p-1} x ∈ Z p − 1 y = a x m o d p y = a^x \bmod p y = a x m o d p h : h: h :
秘密鍵(署名鍵 ): x x x 検証鍵 ): y , α , p y, \alpha, p y , α , p
署名
( t , s ) (t, s) ( t , s ) r ∈ Z p − 1 ∗ r \in \mathbb{Z}_{p-1}^* r ∈ Z p − 1 ∗
t ≡ α r m o d p t \equiv \alpha^r \bmod p t ≡ α r m o d p s ≡ r − 1 ( m − x r ) m o d p − 1 s \equiv r^{-1}(m - xr) \bmod p - 1 s ≡ r − 1 ( m − x r ) m o d p − 1
s ≡ r − 1 ( h ( m ) − x r ) m o d p − 1 s \equiv r^{-1} (h(m) - xr) \bmod p - 1 s ≡ r − 1 ( h ( m ) − x r ) m o d p − 1
検証
α m ≡ y t t s m o d p ( α h ( m ) ≡ y t t s m o d p ) \alpha^m \equiv y^t t^s \bmod p \quad (\alpha^{h(m)} \equiv y^t t^s \bmod p) α m ≡ y t t s m o d p ( α h ( m ) ≡ y t t s m o d p )
y t t s ≡ ( α x ) t ⋅ α r ⋅ m − x t r ≡ α m y^t t^s \equiv (\alpha^x)^t \cdot \alpha^{r \cdot \frac{m - xt}{r}} \equiv \alpha^m
y t t s ≡ ( α x ) t ⋅ α r ⋅ r m − x t ≡ α m
偽造について, gcd ( v , p − 1 ) = 1 \gcd(v, p - 1) = 1 g cd( v , p − 1 ) = 1 v , u v, u v , u
t = α u y v m o d p , s = − t v − 1 m o d p − 1 t = \alpha^u y^v \bmod p, s = -tv^{-1} \bmod p - 1 t = α u y v m o d p , s = − t v − 1 m o d p − 1 m = s u m o d p − 1 m = su \bmod p - 1 m = s u m o d p − 1 t s ≡ α s u y s v ≡ α m y − t m o d p t^s \equiv \alpha^{su} y^{sv} \equiv \alpha^m y^{-t} \bmod p t s ≡ α s u y s v ≡ α m y − t m o d p
( t , s ) (t, s) ( t , s ) m m m
偽造防止のためには, 文書 m m m
アメリカの連邦標準技術局(NIST)により提案されたディジタル署名標準 . ElGmal署名を基にして作られている. (署名サイズが小さい)
鍵生成
素数 p , q p, q p , q q ∣ ( p − 1 ) q \ |\ (p - 1) q ∣ ( p − 1 ) Z p ∗ \mathbb{Z}_p^* Z p ∗ q q q α \alpha α
x ∈ Z q x \in \mathbb{Z}_q x ∈ Z q y = a x m o d p y = a^x \bmod p y = a x m o d p h : h: h :
秘密鍵(署名鍵 ): x x x 検証鍵 ): y , α , p , q y, \alpha, p, q y , α , p , q
署名
( t , s ) (t, s) ( t , s ) r ∈ Z p − 1 ∗ r \in \mathbb{Z}_{p-1}^* r ∈ Z p − 1 ∗
t ≡ ( α r m o d p ) m o d q t \equiv (\alpha^r \bmod p) \bmod q t ≡ ( α r m o d p ) m o d q s ≡ r − 1 ( h ( m ) + x t ) m o d q s \equiv r^{-1} (h(m) + xt) \bmod q s ≡ r − 1 ( h ( m ) + x t ) m o d q
検証
t ≡ ( α h ( m ) s − 1 y t s − 1 m o d p ) m o d q t \equiv (\alpha^{h(m) s^{-1}} y^{ts^{-1}} \bmod p) \bmod q t ≡ ( α h ( m ) s − 1 y t s − 1 m o d p ) m o d q
電子現金や電子投票など, 内容については知られたくない が, 署名は付けて内容を保証したいという状況のときに利用する.
ネットワーク上では通信相手が正しい相手かどうかを確認する手段が必要(なりすましの可能性を排除したい)
認証を実現する方法:
使い捨てパスワード（ワンタイムパスワード）を利用
共通鍵暗号を利用
公開鍵暗号を利用
ディジタル署名を利用
使い捨てパスワードを利用した認証
f f f n n n r r r
使い捨てパスワードを生成し, 安全な場所に記憶する. p 1 = f ( r ) , p 2 = f ( f ( r ) ) , ⋯ , p n = f ( ⋯ ( f ( r ) ) ⋯ ) p_1 = f(r), p_2 = f(f(r)), \cdots, p_n = f(\cdots(f(r)) \cdots) p 1 = f ( r ) , p 2 = f ( f ( r ) ) , ⋯ , p n = f ( ⋯ ( f ( r ) ) ⋯ ) p n p_n p n
使捨てパスワード生成器を利用
共通鍵暗号を利用した認証
E K E_K E K D K D_K D K K K K
認証手順: P P P V V V
V ⇒ P V \Rightarrow P V ⇒ P r r r x = E K ( r ) x = E_K(r) x = E K ( r ) P P P P ⇒ V P \Rightarrow V P ⇒ V x x x r = D K ( x ) r = D_K(x) r = D K ( x ) r ′ r' r ′ y = E K ( r ′ ) y = E_K(r') y = E K ( r ′ ) V V V r ′ = D K ( y ) r' = D_K(y) r ′ = D K ( y ) r r r r ′ r' r ′
公開鍵暗号を利用した認証
E K e E_{K_e} E K e D K d D_{K_d} D K d K e K_e K e K d K_d K d
認証手順: P P P V V V
V ⇒ P V \Rightarrow P V ⇒ P r r r x = E K e ( r ) x = E_{K_e(r)} x = E K e ( r ) P P P P ⇒ V P \Rightarrow V P ⇒ V t = D K d ( x ) t = D_{K_d(x)} t = D K d ( x ) V V V t t t r r r
ディジタル署名を利用した認証
V K V_K V K S K S_K S K K e K_e K e K S K_S K S
認証手順: P P P V V V
V ⇒ P V \Rightarrow P V ⇒ P r r r P P P P ⇒ V P \Rightarrow V P ⇒ V t = S K S ( x ) t = S_{K_S(x)} t = S K S ( x ) V V V 検証 V K e ( r , t ) V_{K_e(r, t)} V K e ( r , t )
1985年 Goldwasser, Micali, Rackoff により提案
秘密に関する知識は一切漏らさず, その秘密をもっているという事実のみを相手に証明する
性質:
完全性 : 検証者は証明者の主張が真 であるとき, 圧倒的に高い確率で 真であると判定する健全性 : 検証者は証明者の主張が偽 であるとき, 圧倒的に高い確率で 偽であると判定する零知識性 : 検証者は証明者から何の知識も得られない
状況:
V V V P P P P P P P P P V V V
零知識対話証明を利用した認証方式であるFiat-Shamir認証方式, あるいは, 高次Fiat-Shamir方式の具体的な数値例を示せ. ただし, Fiat-Shamir認証方式の繰り返し回数は1回で良い.
Fiat-Shamir認証方式:
二つの素数：p = 101 , q = 23 p = 101, q = 23 p = 1 0 1 , q = 2 3 n = p × q = 2323 n = p \times q = 2323 n = p × q = 2 3 2 3
s ∈ Z n ∗ s \in \mathbb{Z}_n^* s ∈ Z n ∗ s 1 = 5 , s 2 = 7 , s 3 = 3 s_1 = 5, s_2 = 7, s_3 = 3 s 1 = 5 , s 2 = 7 , s 3 = 3 v = s 2 m o d n v = s^2 \bmod n v = s 2 m o d n v 1 = 25 , v 2 = 49 , v 3 = 9 v_1 = 25, v_2 = 49, v_3 = 9 v 1 = 2 5 , v 2 = 4 9 , v 3 = 9
認証手順において、乱数 r = 13 r = 13 r = 1 3 x = r 2 m o d n = 169 x = r^2 \bmod n = 169 x = r 2 m o d n = 1 6 9 V V V
e i = { 0 , 1 } e_i = \lbrace 0, 1 \rbrace e i = { 0 , 1 } e 1 = 1 , e 2 = 0 , e 3 = 1 e_1 = 1, e_2 = 0, e_3 = 1 e 1 = 1 , e 2 = 0 , e 3 = 1 P P P
y i = s e i ⋅ r m o d n = 195 y_i = s^{e_i} \cdot r \bmod n = 195 y i = s e i ⋅ r m o d n = 1 9 5 V V V
V V V y i 2 y_i^2 y i 2 v e i ⋅ x v^{e_i} \cdot x v e i ⋅ x y i 2 = 857 = v e i ⋅ x y_i^2 = 857 = v^{e_i} \cdot x y i 2 = 8 5 7 = v e i ⋅ x
1 2 3 4 5 6 7 py .\fiat-shamir.py n = 2323 x = 169 y = 195, y^2 = 857 v1 = 25, v2 = 49, v3 = 9 y2 = 857
これまでに紹介してきた暗号技術を利用することで、ネットワーク上で安全に利用できる様々なシステムを実現
システムの例:
電子現金の必須条件 ：完全情報化, 安全性, 匿名性
完全情報化 ：現金が完全に情報のみで自立して実現されていること安全性 ：電子現金のコピー, 偽造等による不正利用ができないこと匿名性 ：利用者の購買に関するプライバシが, 小売店や電子現金発行・決済者が結託しても露見しないことオフライン検証性 : 小売店での電子現金支払いのときの処理がセンターなどに問い合わせることなく, オフラインで処理できること譲渡可能性 : 電子現金の他人への譲渡が可能であること分割利用可能性 : 1回発行された電子現金を, 利用合計金額が額面の金額になるまで何回でも使うことができること
電子財布の発行：
銀行 B B B i i i ( s i , v i ) (s_i, v_i) ( s i , v i ) v i v_i v i B B B S B ( v i ) S_B(v_i) S B ( v i ) ( i , s i , v i , S B ( v i ) , v B ) (i, s_i, v_i, S_B(v_i), v_B) ( i , s i , v i , S B ( v i ) , v B )
支払処理:
電子財布 i i i j j j x x x
この方式では, 支払い時に下ろした金額と同じ金額を支払うことが前提
支払額はお金を銀行から下ろした後に決定することが多いので, 下ろした金額以内の任意の金額で支払いができる方が利用しやすい
電子現金の額面の金額を RSA 暗号のべきの値 e e e
例:
1円: e = 3 e = 3 e = 3
2円: e = 5 e = 5 e = 5
4円: e = 7 e = 7 e = 7
8円: e = 11 e = 11 e = 1 1
不正投票の防止 ：選挙管理簿に登録されている有権者のみが投票権をもち, 1回のみ投票ができる改ざん/水増しの防止 ：正しく投票された投票結果が改ざんされたり, 水増しされたりしない無記名性 ：誰が誰に投票したかは秘密である公平性 ：選挙が終了するまで, 誰も投票の途中経過を知って利用することができない無証拠性 ：誰に投票したかの証拠となるものがない
ミックスネット方式(Mixnet)
ブラインド署名を利用した方式
高次剰余暗号を利用した方式
マルチパーティプロトコルを利用した方式
U 1 , ⋯ , U n : n U_1, \cdots, U_n: n U 1 , ⋯ , U n : n D : D: D : D ∉ { U 1 , ⋯ , U n } D \notin \lbrace U_1, \cdots, U_n \rbrace D ∈ / { U 1 , ⋯ , U n } p : p: p : n < p n < p n < p s ∈ Z p : \color{red}{s \in \mathbb{Z}_p}: s ∈ Z p : 秘密
各利用者 U i U_i U i d i ∈ Z p d_i \in \mathbb{Z}_p d i ∈ Z p d i d_i d i i ≠ j i \neq j i = j d i ≠ d j d_i \neq d_j d i = d j D D D U i U_i U i s i ∈ Z p s_i \in \mathbb{Z}_p s i ∈ Z p
(k, n)しきい値法 :
n 人のうち任意の k 人のシェアを集めると秘密s を復元できる.
k 人より少ない人数のシェアを集めても秘密s を復元できない
視覚的に秘密情報を復元する秘密分散方式
秘密分散方式と零知識対話証明 を用いて、検証可能秘密分散方式 を実現
秘密 s s s s s s c ( s ) c(s) c ( s ) U i , i = 1 , ⋯ , n U_i, i = 1, \cdots, n U i , i = 1 , ⋯ , n
分配者は, 秘密分散方式を用いて, 利用者 U i , i = 1 , ⋯ , n U_i, i = 1, \cdots, n U i , i = 1 , ⋯ , n s i s_i s i
分配者は, 各利用者のシェアが上記の手順で正しく処理されていることを零知識対話証明 を用いて示す.
検証:
利用者 U i U_i U i α s i \alpha^{s_i} α s i G 0 G 1 d i 1 G 2 d i 2 ⋯ G k − 1 d i k − 1 G_0 G_1^{d_i^1} G_2^{d_i^2} \cdots G_{k-1}^{d_i^{k-1}} G 0 G 1 d i 1 G 2 d i 2 ⋯ G k − 1 d i k − 1 p p p s i s_i s i
Shamirの(3,3)しきい値秘密分散方式の具体的な数値例を示せ.
p = 11 p = 11 p = 1 1 U 1 , U 2 , U 3 : U_1, U_2, U_3: U 1 , U 2 , U 3 : d 1 = 1 , d 2 = 2 , d 3 = 3 : d_1 = 1, d_2 = 2, d_3 = 3: d 1 = 1 , d 2 = 2 , d 3 = 3 : s = 7 : \color{red}{s = 7}: s = 7 :
ランダム でk − 1 k - 1 k − 1 f ( x ) = 7 + 6 x + 5 x 2 f(x) = 7 + 6x + 5x^2 f ( x ) = 7 + 6 x + 5 x 2
シェアの生成
s 1 = f ( d 1 ) = 7 + 6 + 5 m o d 11 = 7 s_1 = f(d_1) = 7+6+5 \bmod 11 = 7 s 1 = f ( d 1 ) = 7 + 6 + 5 m o d 1 1 = 7 s 2 = f ( d 2 ) = 7 + 12 + 20 m o d 11 = 6 s_2 = f(d_2) = 7+12+20 \bmod 11 = 6 s 2 = f ( d 2 ) = 7 + 1 2 + 2 0 m o d 1 1 = 6 s 3 = f ( d 3 ) = 7 + 18 + 45 m o d 11 = 4 s_3 = f(d_3) = 7+18+45 \bmod 11 = 4 s 3 = f ( d 3 ) = 7 + 1 8 + 4 5 m o d 1 1 = 4
秘密の復元: ( d 1 , s 1 ) , ( d 2 , s 2 ) , ( d 3 , s 3 ) (d_1, s_1), (d_2, s_2), (d_3, s_3) ( d 1 , s 1 ) , ( d 2 , s 2 ) , ( d 3 , s 3 ) f ( x ) f(x) f ( x )
秘密 s = f ( 0 ) = 7 s = f(0) = 7 s = f ( 0 ) = 7
1 2 3 4 5 py .\shamir_tn_threshold.py original: 7 shares: [(1 , 7 ), (2 , 6 ), (3 , 4 )] restored: 7
データを秘匿したまま結合分析
秘密分散法を用いた方式（マルチパーティプロトコル）
準同形暗号を用いた方式
完全準同形暗号を用いた方式
Garbled circuit を用いた方式
計算機が処理する関数 f f f
a , b ∈ { 0 , 1 } a, b \in \lbrace 0, 1 \rbrace a , b ∈ { 0 , 1 }
AND：a ⋅ b a \cdot b a ⋅ b
NOT：a ‾ = 1 − a \overline{a} = 1 - a a = 1 − a
XOR：a ⊕ b = a + b − 2 a ⋅ b a \oplus b = a + b - 2a \cdot b a ⊕ b = a + b − 2 a ⋅ b
加算(減算) と乗算ができれば, 任意の処理ができることになる
計算について
