100日後にエンジニアになるキミ - 62日目 - プログラミング - 暗号について #Python

昨日までのはこちら

暗号について

暗号とは何でしょうか？

暗号は第三者が見ても特別な知識なしでは読めないように変換する手法のことを言います。

初期の古典暗号は、多くは紙と鉛筆のみで暗号化を行いますが、多少の道具を用いていました。

種類としては

古典暗号

暗号の作り方も鍵も秘密のアルゴリズムのみで数学的な安全性評価なし

換字式暗号
転置式暗号
スキュタレー暗号
シーザー暗号

現代暗号

暗号アルゴリズムは公開され、鍵のみが秘密
暗号・復号のアルゴリズムは公開されているためプログラムとして実装可能
暗号の安全性は計算量を基に議論する

共通鍵暗号系:DES暗号,AES暗号
公開鍵暗号系:RSA暗号,ElGamal暗号

こんな感じです。

暗号関連用語

以下に暗号で使われる用語を解説する

以下に暗号で使われる用語を解説します。

用語	説明
平文 (plaintext)	暗号化される前の文。
暗号文 (ciphertext)	平文を、独特の表記法によって第三者が読み解けないようにした通信文。
鍵 (key)	表記法のパラメータ。鍵が異なると平文が同じでも暗号文が異なる。
セキュリティパラメータ (security parameter)	暗号の安全性を表す尺度。鍵のサイズなどを指定する。
暗号化 (encryption; encode, encipher)	表記法に従って平文を暗号文に変換すること。
復号 (decryption; decode, decipher)	表記法に従って暗号文を平文に戻すこと。
攻撃 (attack)	暗号化に用いられた表記法の特定あるいは鍵を探索する行為。解読ともいう。
暗号解読 (cryptanalysis)	受信者以外の第三者が暗号文を通信文に戻そうとすること。
共通鍵 (common key; symmetric key)	共通鍵暗号において、暗号化にも復号にも用いられる鍵。秘密鍵ということもある。
公開鍵 (public key)	公開鍵暗号において、暗号化に使用する鍵。
秘密鍵 (private key)	公開鍵暗号において、復号に使用する鍵。

シーザー暗号(Caesar cipher)

「お前もか！！」で有名なシーザーさんの使っていた暗号だそうです。

方式は文字をシフトさせるだけのお手軽暗号化です。

鍵は何文字、という部分だけで特に秘密なものはありません

頑張れば読めてしまうであろう暗号ですね。
それでも昔は暗号として使えていたというわけです。

実際にプログラムで暗号文を作ってみましょう。

英文字のみをシフトさせるとし
何文字シフトさせるかは可変にしています。

def caesar_cipher_encrypt(plaintext, key):
    cipher = ""
    for p in list(plaintext):
        if 'A' <= p <= 'Z':
            cipher += chr((ord(p) - ord('A') + key)%26 + ord('A'))
        elif 'a' <= p <= 'z':
            cipher += chr((ord(p) - ord('a') + key)%26 + ord('a'))
        else:
            cipher += p
    return cipher

これで暗号化させる関数は出来上がりです、
復号もこれで行う事ができます。

これで暗号化された文字を解読してみましょう。

zdwdvklqr jhvvbxxkd 53pdq ghdwk

text = 'zdwdvklqr jhvvbxxkd 53pdq ghdwk'
for i in range(1,26):
    print(i,caesar_cipher_encrypt(text, i))

1 aexewlmrs kiwwcyyle 53qer hiexl
2 bfyfxmnst ljxxdzzmf 53rfs ijfym
3 cgzgynotu mkyyeaang 53sgt jkgzn
・・・

23 watashino gessyuuha 53man death

これですね！！
23文字シフトさせたやつが答えっぽいです。

スキュタレー暗号

スキュタレー暗号は棒に革紐を巻きつけて平文を書いて
革紐を外したら、それが暗号になるというものです。

元の文字自体は変わらず文字の順番のみが変わるというものです。

このような関数でスキュタレー暗号を作ることができます。

def sq_cipher_encrypt(plaintext, num):
    cipher = ""
    c,b = 0,0
    for i in range(len(plaintext)):
        cipher += plaintext[c]
        if c+num<len(plaintext):
            c+=num
        else:
            b+=1
            c=b
    return cipher

sq_cipher_encrypt('私の戦闘力は53マンです',4)

'私力マのはン戦5で闘3す'

sq_cipher_encrypt('私力マのはン戦5で闘3す',3)

'私の戦闘力は53マンです'

同じ棒がなかったら昔は解読できなかったとか言われているそうで
何事も暗号も辛抱（芯棒）が大事

お後がよろしいようでwww

ヴィジュネル暗号

ヴィジュネル暗号は１５～１６世紀に考えられた換字式の暗号です。

下記のヴィジュネル方陣と鍵を使って暗号化を行います。

例として鍵:arm、平文:CODEとするとヴィジュネル方陣で
aとCの交わりはc , rとOはf , mとDはpというように
暗号文 c, f, p が得られる。

平文が鍵よりも長い場合、鍵を繰り返して用い最後の平文Eはaとの交わりでeとなり、平文:CODEは暗号文:cfpeとなる。

1文字づつシフトする文字が変わるため、鍵がないと複合が難しくなる。

参考:wikipedia

相当長い暗号文が与えられしかもそれがヴィジュネル暗号だと分かっているときは
頑張れば解読可能だったりします。

# 暗号化
def encrypt( plain, key ):
    index , result = 0 , ''
    while index < len(plain):
        index2 = index % len(key)
        p_code = ord(plain[index]) - ord('a')
        k_code = ord(key[index2]) - ord('A')
        result += chr( (p_code + k_code) % 26 + ord('a') )
        index += 1
    return result

# 復号化
def decrypt( cipher, key ):
    index , result = 0 , ''
    while index < len(cipher):
        index2 = index % len(key)
        c_code = ord(cipher[index]) - ord('a')
        k_code = ord(key[index2]) - ord('A')
        result += chr((c_code - k_code) % 26 + ord('a') )
        index += 1
    return result

# 暗号化する文字の指定
plain_text = 'otexintexin birooon'

# キーの指定
key_text = 'otupy'

# 暗号化
cipher_text = encrypt( plain_text , key_text )
print( cipher_text )

# 復号化
decode_text = decrypt( cipher_text , key_text )
print( decode_text )

isesmhsesmhaimsinn
otexintexinbirooon

エニグマ(Enigma)

エニグマは人類史上最も有名な暗号だと思います。
第二次世界大戦でナチス・ドイツが用いたローター式暗号機で幾つかの型があり
暗号機によって作成される暗号も広義にはエニグマと呼ばれるようです。

そもそも名前がかっこいい！！！

仕組みを説明すると死んでしまうのでこちらを参照ください。

エニグマ(wikipedia)

こんなコードでエニグマを再現できるっぽいです。

import random
import copy

class Enigma:

    def __init__(self, s1, s2 = 0, s3 = 0):
        alpha = [chr(i) for i in range(ord("a"), ord("z") + 1)]
        adds = [' ', '?', '.', ',']
        self.orig = alpha+ adds
        self.c_num = len(self.orig)
        self.c_num2 = self.c_num * self.c_num
        self.rotor1 = self.make_rotor(s1)
        self.rotor2 = self.make_rotor(s2)
        self.rotor3 = self.make_rotor(s3)
        self.reflect = self.make_rotor(s1)
        self.plug = self.make_plug()

    def make_rotor(self, seed = 0):
        random.seed(seed)
        alpha = copy.copy(self.orig)
        random.shuffle(alpha)
        return alpha

    def make_plug(self, seed = 0):
        random.seed(seed)
        plug = copy.copy(self.orig)
        rp = random.sample(range(self.c_num), 6)
        for idx in range(0, 6, 2):
            plug[rp[idx]] , plug[rp[idx + 1]] = (plug[rp[idx + 1]] , plug[rp[idx]],)
        return plug

    def rotate(self, idx):
        self.rotor1.append(self.rotor1.pop(0))
        if idx % self.c_num == 0 and idx / self.c_num != 0:
            self.rotor2.append(self.rotor2.pop(0))
        if idx % self.c_num2 == 0 and idx / self.c_num2 != 0:
            self.rotor3.append(self.rotor3.pop(0))

    def encode_c(self, ch):
        char = self.plug[self.orig.index(ch)]
        char = self.rotor1[self.orig.index(char)]
        char = self.rotor2[self.orig.index(char)]
        char = self.rotor3[self.orig.index(char)]
        if self.reflect.index(char) % 2 == 0:
            char = self.reflect[self.reflect.index(char) + 1]
        else:
            char = self.reflect[self.reflect.index(char) - 1]
        char = self.orig[self.rotor3.index(char)]
        char = self.orig[self.rotor2.index(char)]
        char = self.orig[self.rotor1.index(char)]
        char = self.orig[self.plug.index(char)]
        return char

    def encode(self, string):
        code_string = ""
        for idx, char in enumerate(string):
            code_string += self.encode_c(char)
            self.rotate(idx)
        return code_string

# シードを設定
seed = 1
# 平文を設定
plain = 'hirabunoyabun'

# 暗号化
enigma = Enigma(seed)
enc = enigma.encode(plain)
print("Encrypt : " , 'Seed : ' , seed , enc)

# 復号化
enigma = Enigma(seed)
dec = enigma.encode(enc)
print("Decrypt : ", 'Seed : ' , seed , dec )

# 復号化(シード違い)
seed2 = 2
enigma = Enigma(seed2)
dec = enigma.encode(enc)
print("Decrypt : ", 'Seed : ' , seed2 ,  dec  )

Encrypt : Seed : 1 adjpiqisrgxgp
Decrypt : Seed : 1 hirabunoyabun
Decrypt : Seed : 2 vssxdz,rqyhwq

シードが分かってないと復号は大変です。

RSA暗号

RSA暗号は桁数が大きい合成数の素因数分解問題が困難であることを
安全性の根拠とした公開鍵暗号の一つです。

現在、公開鍵暗号アルゴリズムの中では広く使われています。

仕組み

RSA暗号は

1.鍵生成アルゴリズム(公開鍵と秘密鍵の生成)
2.暗号化アルゴリズム(公開鍵による暗号化)
3.復号アルゴリズム(秘密鍵による複合)

からなります。

鍵の生成には2つの素数 P , Q を用いて　数値　n を作ります。
この時に用いる素数の桁数(長さ)が暗号の強度になります。

n = p * q

例：p,q (3,5) として

n = p * q = 3 * 5 = 15

次にφ(n)=(p-1)(q-1)を求める
(自然数 nに関してn と互いに素な n 未満の自然数の個数を φ(n) とする)

例：
φ(n) = (3-1)(5-1) = 8

公開鍵は(e , n)となりますがe は(p - 1)(q - 1)未満かつ
(p - 1)(q - 1)と互いに素な数から適当に選べば良いようです。

今回は 3 とすることとします。

そうすると　公開鍵は (e, n) = (3, 15) となります。

秘密鍵 d は d * e = l(modφ(n)) を解くことで求められます。
今回は秘密鍵 d = 3 とします。

暗号化と復号化

暗号化（平文 m から暗号文 c を作成する）： c = 𝑚𝑒 mod n
復号　（暗号文 c から元の平文 m を得る）： m = 𝑐𝑑 mod n

平文 m = 3 の場合(上記で n = 15 , e = 3 , d = 3)

暗号化 : c = 33 mod 15 = 27 mod 15 = 12
復号　 : m = 123 mod 15 = 1728 mod 15 = 3

RSAでは2048bit以上の大きさの鍵であれば安全であると言われていますが
コンピュータの進歩とともに、小さな鍵は破られています。

以下はRSA暗号化の例です。

# RSA暗号の例
import random
import fractions
import warnings 
warnings.filterwarnings('ignore')

class RSA():
    plaintext = ""
    ciphertext = []
    _e = _d = _n = 0
    _p = _q = 0
    _l = 0

    def __init__(self):
        pass
    def __del__(self):
        pass

    def set_plaintext(self,str):
        self.plaintext = str

    def _random(self):
        digit = 10
        return random.randrange(10**(digit - 1),10**digit)

    def get_public_key(self):
        return (self._e, self._n)

    def get_private_key(self):
        return (self._d, self._n)

    def get_key_data(self):
        return (self._l, self._p, self._q)

    def _lcm(self,p,q):
        return (p * q) // fractions.gcd(p, q)

    def _etension_euclid(self,x,y):
        c0, c1 = x, y
        a0, a1 = 1, 0
        b0, b1 = 0, 1
        while c1 != 0:
             m = c0 % c1
             q = c0 // c1
             c0, c1 = c1, m
             a0, a1 = a1, (a0 - q * a1)
             b0, b1 = b1, (b0 - q * b1)
        return c0, a0, b0

    def _is_prime_number(self,q):
        cnt = 50
        q = abs(q)
        if q == 2: return True
        if q < 2 or q & 1 == 0: return False
        d = (q - 1) >> 1
        while d & 1 == 0:
            d >>= 1
        for i in range(cnt):
            a = random.randint(1,q - 1)
            t = d
            y = pow(a, t, q)
            while t != q - 1 and y != 1 and y != q - 1: 
                y = pow(y, 2, q)
                t <<= 1
            if y != q - 1 and t & 1 == 0:
                return False
        return True

    def generate_key(self,p = 0,q = 0,e = 0,d = 0,n = 0,l = 0):
        if p == 0:
            while True:
                p = self._random()
                if self._is_prime_number(p):break
        self._p = p
        if q == 0:
            while True:
                q = self._random()
                if self._is_prime_number(q) and p != q:break
        self._q = q
        if n == 0:
            n = p * q
        self._n = n
        if l == 0:
            l = self._lcm(p - 1, q  - 1)
        self._l = l
        if e == 0:
            while True:
                i = random.randint(2,l)
                if fractions.gcd(i, l) == 1:
                  e = i
                  break
        self._e = e
        if d == 0:
            _c, a, _b = self._etension_euclid(e, l)
            d = a % l
        self._d = d

    def encrypt(self):
        st = ""
        for i in map((lambda x: pow(ord(x), self._e,self._n)),list(self.plaintext)):
            self.ciphertext.append(i)
            st += str(i)
        return st

    def decrypt(self):
        cip = []
        st = ""
        for i in  list(self.ciphertext):
            tmp = chr(pow(i, self._d,self._n))
            cip.append(tmp)
            st += str(tmp)
        return st

# 平文を用意
input_text = '暗号化するよ'
print("平文 m = "  , input_text)

# RSA
rsa = RSA()
rsa.set_plaintext(input_text)
rsa.generate_key(0,0,65537)
l , p , q = rsa.get_key_data()
e , n     = rsa.get_public_key()
d , _n   = rsa.get_private_key()
print("素数 p = " , p)
print("素数 q = " , q)
print("公開鍵 n = " , n)
print("l = " , l )
print("公開鍵 e = " , e)
print("秘密鍵 d = " , d)
print()

# 暗号化
en = rsa.encrypt()
print("C = " , en)

# 複合化
de = rsa.decrypt()
print("P = " ,de)

平文 m = 暗号化するよ
素数 p = 6023748509
素数 q = 9563698961
公開鍵 n = 57609317356848599149
l = 14402329335315287920
公開鍵 e = 65537
秘密鍵 d = 10272622866156722673

C = 30714984511718544149370906887949705420833394532467656627958137219747729009706991832334015687577370336953398010927394738
P = 暗号化するよ

と書いていますが正直RSA良く分かってませんので
間違っていたらすみません。

まとめ

世の中には色々な暗号の仕組みがありWEBでも用いられています。
用語や簡単な暗号化、復号化のしくみは抑えておきましょう。

君がエンジニアになるまであと38日

作者の情報

乙pyのHP：
http://www.otupy.net/

Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter：
https://twitter.com/otupython