# -*- coding:utf-8 -*-
from sympy import prime
import random
import math
import time

T = int(time.time())

def pr_et(m):
  global T
  print(m + ":" + str(int(time.time()) - T))
  T = int(time.time())


def def_E_D(p1, p2):
  t1 = (p1 - 1)
  t2 = (p2 - 1)
  # t1とt2の最小公倍数
  L = (t1 * t2) // math.gcd(t1, t2)
  pr_et("fin_gen_L " + str(L))

  # 1 < E < L
  # gcd(E,L) = 1
  E = random.choice([ i for i in range(2,L) if math.gcd(i, L) == 1 ])
  pr_et("fin_gen_E " + str(E))

  # 1 < D < L
  # (E×D) mod L = 1
  D = random.choice([ i for i in range(2,L) if (E * i) % L == 1 ])
  pr_et("fin_gen_D " + str(D))
  return E, D


if __name__ == '__main__':
  # 暗号文 = 平文^E mod N
  # 平文 = 暗号文^D mod N
  # E、Nの組み合わせが公開鍵
  # D、Nの組み合わせが秘密鍵
  # Nは2つの大きな素数を掛けたもの
  t =  int(time.time())

  # N、E、D算出用素数。101と1101の指定は小さい値にならないようにする為。
  p1 = prime(random.randint(101,1101))
  p2 = prime(random.randint(101,1101))
  while p1 == p2:
    p2 = prime(random.randint(101, 1101))
  pr_et("fin_gen_p12 " + str(p1) + " " + str(p2))

  N = p1 * p2
  pr_et("fin_gen_N " + str(N))
  E, D = def_E_D(p1, p2)

  # 平文"あ"を数字化。ユニコードのコードポイント利用。
  CP = ord("あ")
  pr_et("fin_gen_CP " + str(CP))

  # 暗号化
  ENC = (CP ** E) % N
  pr_et("fin_gen_ENC " + str(ENC))

  # 復号化
  DEC = (ENC ** D) % N
  pr_et("fin_gen_DEC " + str(DEC))

  if CP == DEC:
    print('Success!')
  else:
    print('Failure!')

確認コードのポイント

必ずSuccessになる。
処理自体は、そんなに複雑ではない。
攻撃者は公開鍵(E,N)と暗号化データ(ENC)は取得可能
Ephemeralデータは使わない！=PFS対応でない

素朴な疑問

①E,N,ENCを使って総当たり計算したら、どのくらい時間かかるのだろう？
②暗号化可能な点は上記で理解できる。ただデジタル署名(復号できる＝認証OK)は、どうやって実装してるのだろう？

素朴な疑問①について

確認コードの実行結果

fin_gen_p12 8297 4099:0
fin_gen_N 34009403:0
fin_gen_L 16998504:0
fin_gen_E 12379243:4
fin_gen_D 12788611:2
fin_gen_CP 12354:0
fin_gen_ENC 24181895:99
fin_gen_DEC 12354:285
Success!

そもそも、こんな計算できるの？とも思ったが、できてる。。。

平文 = 暗号文^D mod N
24181895 ** 12788611 % 34009403

E=2379243
N=34009403
ENC=24181895
上記からDECを総当たりで平文出そうとしたら、どれくらい時間かかるの？
う～ん、迷走中。

結局、DECは% Nで求められるので、1 < DEC < N(34009403)になる。
Nは公開鍵に含まれる情報。Nが小さいと、復号化をNパターンでTRYしてみて、結果が自然か？を機械学習で判定できれば、復号化できるのでは？
Nは大きくするのが必須だろう。
メールデータは、最初がReceived: ～とかで始まる前提を活用し、総当たりすれば、Nを少なくできるのでは？
メール本文がhogeだけとかのメールをSMTPSで送ってみて、そのパケットをキャプチャし、復号化をためして見ようかな。。。

素朴な疑問②について

https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%#%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB%E7%BD%B2%E5%90%8D%E6%96%B9%E5%BC%8F%E3%81%B8%E3%81%AE%E5%BF%9C%E7%94%A8

2020-05-03

Diffie-Hellman key exchangeについて

暗号化セキュリティ

参考

Diffie-Hellman で鍵交換しましょ★ - ✲ﾟ｡.ヾ(⌒(ﾉ'ω')ﾉ☆.｡
Diffie-Hellman鍵交換入門 - Qiita
ディフィー・ヘルマン鍵共有 - Wikipedia
原始根
 原始根の定義と具体例（高校生向け） | 高校数学の美しい物語

ポイント

読み方

ディフィー・ヘルマン(ディッフェルと勘違いしてた。。。）

公開鍵暗号の一種

公開鍵暗号 - Wikipedia

暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開できるようにした暗号方式

他にRSAがあり。
※公開鍵暗号は、共通鍵暗号の共有鍵の交換で利用される

素数

正の約数が 1 と自分自身のみ

原子根

（3 以上の）素数 p と 1 以上 p 未満の整数 r が以下の性質を満たすとき r を p に対する原始根と呼ぶ。
「r,r2,⋯,rp−2 のいずれもが p で割って余り 1 でない」
★よく分からないけど、素数に対し存在する、ある条件に合致する整数と考える。
★一つの素数に対し複数存在することあり。例) 素数7の場合、5,3

送受信者間で交換する情報

確認コード

# -*- coding:utf-8 -*-
from sympy import prime
import random
import sym
from sympy.ntheory import is_primitive_root

if __name__ == '__main__':
  # 素数をランダムに設定(100～1100番目の範囲で)
  P = prime(random.randint(101,1101))
  # 選択した素数に対する原始根をランダムに設定
  G = random.choice([i for i in range(1,P) if is_primitive_root(i, P)])
  # 送信者側の乱数設定
  A = random.randint(1,P - 2)
  # 受信者側の乱数設定
  B = random.randint(1,P - 2)
  # 送信者が受信者に以下を通知
  GA_MOD_P = G ** A % P
  # 受信者が送信者に以下を通知
  GB_MOD_P = G ** B % P
  # 送信者が共有鍵を計算
  A_SKEY = GB_MOD_P ** A % P
  # 受信者が共有鍵を計算
  B_SKEY = GA_MOD_P ** B % P
  # 送信者と受信者の共有鍵が同一であることを確認
  if A_SKEY == B_SKEY:
    print('Success!')
  else:
    print('Failure!')

確認コードのポイント

・必ずSuccessになる
・数学の理論として、GB_MOD_P ** A % PとGA_MOD_P ** B % Pが同じになる点を利用し共通鍵を交換
・やりとりする情報は全てephemeral(短命の)=PFS対応
・Opensslの暗号化スイートでDHとDHEがあり。
・DHは証明書のDHパラメタを利用(static DH)
・DHEはDHパラメタを動的に生成

・Ａ,Bが秘密鍵、G,P,GA_MOD_P,GB_MOD_Pが公開鍵

※参考URL
Pythonで数学の勉強：初等整数論 - Qiita
Ntheory Class Reference - SymPy 1.11 documentation
夜でもアッサム: SSL(TLS)のDHとDHEの違い