Geekly Articles each Day

AES-128。 Pythonでの詳现ず実装

自分甚に暗号化するものを曞くずいうアむデアはかなり簡単に生たれたした。別のデビットカヌドを入手する必芁があったため、別のPINコヌドを頭に残したした。 Paranoiaでは、このような情報をオヌプンな圢匏で保存するこずは蚱可されおおらず、サヌドパヌティのサヌビスも䜿甚しおいないため、いく぀かの怜玢の埌、AES芏栌に準拠したした。 远加のモゞュヌルに頌らずに、私はすぐにアルゎリズムを自分で理解しお実装したかったのです。

この蚘事では、アルゎリズムのコンポヌネントに぀いお詳しく説明し、マット郚分を少し掘り䞋げお、Pythonでの実装䟋を瀺したす。 開発では、暙準ラむブラリの䞀郚のみに限定したした。

ちょっずした玹介


Advanced Encryption Standardは、2人のベルギヌの暗号䜜成者Joan DimenずVincent Raymanによっお開発されたRijndaelアルゎリズム[rɛindaːl]の有名な名前です。 アルゎリズムはブロック状で察称的です。 米囜政府機関のデヌタ暗号化暙準ずしお採甚されたした。 最近高く評䟡されおいる囜家安党保障局は文曞を保存するためにそれを䜿甚しおいたすSECRETレベルたで、128ビットのキヌによる暗号化が䜿甚され、TOP SECRET情報には192たたは256ビットのキヌが必芁です。 高い暗号匷床に加えお、アルゎリズムは最も耇雑な数孊ではありたせん。

倚くの暗号化


動䜜させるには、暗号化オブゞェクトずしおのバむトセットず、埩号化䞭に必芁ずなる秘密キヌが必芁です。 長いキヌを頭に入れおおくのは䞍䟿であり、キヌの長さは128ビットで、アクセスできないほど十分であるず考えられおいるため、オプション192/256を芋おいたせん。 さらに、 ここで述べたように 、特定の条件䞋では、長いキヌは安定性に遅れるこずがありたす。

いく぀かの衚蚘法を玹介したす。

アルゎリズムには4぀の倉換があり、それぞれ独自の方法でStateの状態に圱響を䞎え、最終的に結果を導きたす SubBytes、ShiftRows、MixColumns 、 AddRoundKey 。 䞀般的な暗号化スキヌムは次のように衚すこずができたす。
画像
最初に、State配列には、匏State [r] [c] = input [r + 4c]、r = 0.1 ... 4;に埓っお入力倀が入力されたす。 c = 0.1..Nb ぀たり、列で。 16バむトのブロックは䞀床に暗号化されたす。
画像

アルゎリズムはバむトで動䜜し、それらを有限䜓たたはガロア䜓GF2 8 の芁玠ず芋なしたす。 括匧内の数字は、フィヌルド芁玠の数たたはその力です。 䜓GF2 8 の芁玠は最倧7の次数の倚項匏であり、係数の行で指定できたす。 バむトは、倚項匏ずしお非垞に簡単に衚珟できたす。 たずえば、バむト{1,1,1,0,0,0,1,1,1}は、フィヌルド芁玠1x 7 + 1x 6 + 1x 5 + 0x 4 + 0x 3 + 0x 2 + 1x 1 + 1x 0 = 1x 7 +に察応したす。 1x 6 + 1x 5 + x +1。 フィヌルド芁玠を操䜜するずいう事実は、加算および乗算挔算のルヌルを倉曎するため、非垞に重芁です。 これに぀いおは少し埌で觊れたす。

次に、各倉換に぀いお詳现に怜蚎したす。

SybButes

倉換は、Stateの各バむトをSbox定数テヌブルの察応するバむトに眮き換えるこずです。 Sbox芁玠の倀は16進衚蚘で衚されたす。 テヌブル自䜓は、既知のフィヌルドGF2 8 を倉換するこずによっお取埗されたした
画像
Stateの各バむトは、16進衚蚘で{xy}ずしお衚すこずができたす。 次に、行xず列yの亀点にある芁玠に眮き換えたす。 たずえば、{6e}は{9f}に、{15}は{59}に眮き換えられたす。

ShiftRows

簡単な倉換。 最初の行に1芁玠、2番目に2、3番目に3の埪環巊シフトを実行したす。 れロラむンはシフトされたせん。


MixColumns

この倉換の䞀郚ずしお、Stateの各列は倚項匏ずしお衚され、フィヌルドGF2 8 でx 4 + 1を法ずする固定倚項匏3x 3 + x 2 + x + 2で乗算されたす。 。 暙準の公匏ドキュメントで提䟛されおいる同等のマトリックス゚ントリを芋るず、図はより単玔になりたす。

行列を乗算する堎合、a ijの倀は、最初の行列のi番目の行ず2番目の行列のj番目の列の察応する芁玠の積の合蚈ずしお取埗されたす。

ここで、加算ず乗算の通垞のルヌルの動䜜䞍胜を思い出す必芁がありたす。
新しいルヌル

圓然、これらは最終フィヌルドの算術の䞀般的な芏則ではありたせんが、アルゎリズムの䞀郚ずしお、暗号化のために3぀の定数ず埩号化のために4぀の定数を掛ける必芁があるため、このようなロヌカルラむフハックで十分です。
MixColumnsずShiftRowsは、暗号に拡散を远加したす。

AddRoundKey

倉換により、Stateの各芁玠ずRoundKeyの察応する芁玠のビット単䜍のXORが生成されたす。 RoundKeyはStateず同じサむズの配列であり、KeyExpansion関数を䜿甚しお秘密鍵に基づいおラりンドごずに構築されたす。これに぀いおは埌で怜蚎したす。

KeyExpansion

この補助倉換は、ラりンドキヌのセット-KeyScheduleを圢成したす。 KeyScheduleは、Nb *Nr + 1列たたはNr + 1ブロックで構成される長いテヌブルで、それぞれのサむズはStateず同じです。 最初のラりンドキヌは、蚈算した秘密鍵に基づいお蚘入されたす。
KeySchedule [r] [c] = SecretKey [r + 4c]、r = 0.1 ... 4; c = 0,1..Nk。

KeyScheduleでは、さらなる操䜜が可胜になるようにバむトを入力する必芁があるこずは明らかです。 このアルゎリズムをホヌム暗号化に䜿甚する堎合、数字のシヌケンスを頭に保存するこずはたったく䟿利ではないため、実装ではKeyExpansionはプレヌンテキスト入力を取埗し、各文字にord()を䜿甚しお、結果をKeyScheduleセルに曞き蟌みたす。 これは制限を意味したす長さが16文字以䞋であり、バむトをord()文字のord()バむナリで255たたは11111111を超える倀を返すべきではありたせん。そうでない堎合、出力で䞍正な暗号化を受け取りたす。 ロシア語のキヌを䜿甚するず、暗号化が機胜しないこずが刀明したした。



図は、AES-128のKeyScheduleレむアりトを瀺しおいたす。4列の11ブロック。 アルゎリズムの他のバリ゚ヌションでは、Nb列のNr + 1ブロックがそれぞれありたす。 次に、空のスペヌスを埋める必芁がありたす。 倉換のために、定数テヌブルが再び定矩されたす-Rcon-倀は16進数システムです。



KeySchedule補充アルゎリズム

この補助的な倉換は、アルゎリズムではMixColumnsで数孊が認識された埌、曞面で最もボリュヌムがあり、おそらく最も耇雑です。 暗号化キヌは、4 * Nk個の芁玠で構成する必芁がありたすこの䟋では16。 しかし、私たちはこれをすべお家庭で䜿甚するために行っおいるので、誰もが16文字のキヌを思い぀いおそれを芚えおいるずは限りたせん。 したがっお、長さが16未満の行が入力に到着するず、KeyScheduleのIは倀{01}を暙準に远加したす。
KeyExpansionコヌド
 def key_expansion(key): key_symbols = [ord(symbol) for symbol in key] # ChipherKey shoul contain 16 symbols to fill 4*Nk table. If it's less # complement the key with "0x01" if len(key_symbols) < 4*nk: for i in range(4*nk - len(key_symbols)): key_symbols.append(0x01) # make ChipherKey(which is base of KeySchedule) key_schedule = [[] for i in range(4)] for r in range(4): for c in range(nk): key_schedule[r].append(key_symbols[r + 4*c]) # Comtinue to fill KeySchedule for col in range(nk, nb*(nr + 1)): # col - column number if col % nk == 0: # take shifted (col - 1)th column... tmp = [key_schedule[row][col-1] for row in range(1, 4)] tmp.append(key_schedule[0][col-1]) # change its elements using Sbox-table like in SubBytes... for j in range(len(tmp)): sbox_row = tmp[j] // 0x10 sbox_col = tmp[j] % 0x10 sbox_elem = sbox[16*sbox_row + sbox_col] tmp[j] = sbox_elem # and finally make XOR of 3 columns for row in range(4): s = key_schedule[row][col - 4]^tmp[row]^rcon[row][col/nk - 1] key_schedule[row].append(s) else: # just make XOR of 2 columns for row in range(4): s = key_schedule[row][col - 4]^key_schedule[row][col - 1] key_schedule[row].append(s) return key_schedule

前述のように、KeyScheduleはAddRoundKeyの倉換に䜿甚されたす。 初期化ラりンドでは、ラりンドキヌは最初に0、..、3の数字の列、4、..、7などの数字になりたす。 AddRoundKeyの党䜓的なポむントは、XOR状態ずラりンドキヌを生成するこずです。

実際、これはすべお暗号化プロセスに関するものです。 暗号化されたバむトの出力配列は、匏output [r + 4c] = State [r] [c]、r = 0.1 ... 4;に埓っおStateからコンパむルされたす。 c = 0.1..Nb その間、蚘事は遅れおいるため、ここですぐに埩号化手順に぀いお説明したす。

すぐに解読に぀いお


ここでの考え方は単玔です。同じキヌワヌドを䜿甚しお暗号化倉換ず逆の倉換シヌケンスを実行するず、元のメッセヌゞが取埗されたす。 このような逆倉換は、 InvSubBytes、InvShiftRows、InvMixColumns、およびAddRoundKeyです。 埩号化アルゎリズムの䞀般的なスキヌム

ラりンドキヌをAddRoundKeyに远加する順序は、Nr + 1から0の逆順であるこずに泚意しおください。最初は、暗号化ず同様に、状態テヌブルは入力バむトの配列から圢成されたす。 その埌、各ラりンドで倉換が実行され、その最埌に埩号化されたファむルを取埗する必芁がありたす。 倉換の順序が少し倉曎されたした。 最初のInvSubBytesたたはInvShiftRowsは重芁ではありたせん。1぀はバむト倀で動䜜し、2぀目はこれらの倀を倉曎せずにバむトを再配眮したすが、暙準の擬䌌コヌドでの倉換シヌケンスに埓いたした。

InvSubBytes

SubBytesずたったく同じように機胜したすが、眮き換えはInvSbox定数テヌブルから行われたす。

残りの逆倉換も、盎接察応するものず非垞によく䌌おいるため、コヌドではそれらに個別の関数を遞択しおいたせん。 倉換を蚘述する各関数にはinv倉数がありたす。 False堎合、関数は通垞モヌドたたは盎接モヌド暗号化で動䜜し、 True堎合-逆モヌド埩号化で動䜜したす。
コヌド
 def sub_bytes(state, inv=False): if inv == False: # encrypt box = sbox else: # decrypt box = inv_sbox for i in range(len(state)): for j in range(len(state[i])): row = state[i][j] // 0x10 col = state[i][j] % 0x10 # Our Sbox is a flat array, not a bable. So, we use this trich to find elem: box_elem = box[16*row + col] state[i][j] = box_elem return state


InvShiftRows

倉換は、状態の最初の行に1芁玠、2番目に2芁玠、3番目に3芁玠ず぀右に埪環したす。 れロ線は回転したせん。

コヌドの説明 left_shift/right_shift(array, count)入力arrayを察応する方向にcount回回転させたす
コヌド
 def shift_rows(state, inv=False): count = 1 if inv == False: # encrypting for i in range(1, nb): state[i] = left_shift(state[i], count) count += 1 else: # decryption for i in range(1, nb): state[i] = right_shift(state[i], count) count += 1 return state


InvMixColumns

操䜜は同じですが、各State列には異なる倚項匏{0b} x 3 + {0d} x 2 + {09} x + {0e}が乗算されたす。 マトリックス圢匏では、次のようになりたす。

たたは既補の数匏。 もちろん、すべおの倀は16進衚蚘です。

ここでは、数孊に向かっお脱線し、{02}より倧きい定数で乗算する関数を取埗する方法を説明する必芁がありたす。 私が蚀ったように、それらは{01}ず{02}を介しおそれらを分解するこずによっお埗られたす、すなわち
コンバヌゞョン数
n * {03} = n *{02} + {01}= n * {02} + n * {01}
n * {09} = n *{08} + {01}= n * {02} * {02} * {02} + n * {01}
n * {0b} = n *{08} + {02} + {01}= b * {02} * {02} * {02} + n * {02} + n * {01}
n * {0d} = n *{08} + {04} + {01}= n * {08} + n * {04} + n * {01} = n * {02} * {02} * {02} + n * {02} * {02} + n * {01}
n * {0} = n *{08} + {04} + {02} = n * {08} + n * {04} + n * {02} = n * {02} * {02} * { 02} + n * {02} * {02} + b * {02}

もちろん、別の方法で数字を分解するこずもできたすが、分解が個人的に怜蚌されたす
n * {09} = n * {03} + n * {03} + n * {03}
察応する関数を呌び出すず、間違った結果が埗られたす結果を含む参照テヌブルは、゜ヌスリストのリンクの1぀にありたす。 圌は、代替のコメント付きバヌゞョンの蚈算を特別に残したした。これは、それらがより理解しやすく、゚レガントであるが、䜕らかの理由で正しく動䜜しないためです。
補助乗算関数
 def mul_by_02(num): if num < 0x80: res = (num << 1) else: res = (num << 1)^0x1b return res % 0x100 def mul_by_03(num): return mul_by_02(num)^num def mul_by_09(num): #return mul_by_03(num)^mul_by_03(num)^mul_by_03(num) - works wrong, I don't know why return mul_by_02(mul_by_02(mul_by_02(num)))^num def mul_by_0b(num): #return mul_by_09(num)^mul_by_02(num) return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(num)^num def mul_by_0d(num): #return mul_by_0b(num)^mul_by_02(num) return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^num def mul_by_0e(num): #return mul_by_0d(num)^num return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^mul_by_02(num)

コヌドの説明 MixColumnsに関するセクションで説明した芏則に埓っお、関数mul_by_<>にGF2 8 の察応する定数を乗算したす。
コヌド
  def mix_columns(state, inv=False): for i in range(nb): if inv == False: # encryption s0 = mul_by_02(state[0][i])^mul_by_03(state[1][i])^state[2][i]^state[3][i] s1 = state[0][i]^mul_by_02(state[1][i])^mul_by_03(state[2][i])^state[3][i] s2 = state[0][i]^state[1][i]^mul_by_02(state[2][i])^mul_by_03(state[3][i]) s3 = mul_by_03(state[0][i])^state[1][i]^state[2][i]^mul_by_02(state[3][i]) else: # decryption s0 = mul_by_0e(state[0][i])^mul_by_0b(state[1][i])^mul_by_0d(state[2][i])^mul_by_09(state[3][i]) s1 = mul_by_09(state[0][i])^mul_by_0e(state[1][i])^mul_by_0b(state[2][i])^mul_by_0d(state[3][i]) s2 = mul_by_0d(state[0][i])^mul_by_09(state[1][i])^mul_by_0e(state[2][i])^mul_by_0b(state[3][i]) s3 = mul_by_0b(state[0][i])^mul_by_0d(state[1][i])^mul_by_09(state[2][i])^mul_by_0e(state[3][i]) state[0][i] = s0 state[1][i] = s1 state[2][i] = s2 state[3][i] = s3 return state


AddRoundKey

XOR挔算のプロパティにより、この倉換はそれ自䜓に反比䟋したす。
a XOR bXOR b = a

したがっお、それを倉曎する必芁はありたせん。 ラりンドキヌのセットは、KeyExpansion関数を䜿甚した暗号化ず同じ方法で圢成されたすが、ラりンドキヌは逆の順序で眮き換える必芁がありたす。
コヌド
 def add_round_key(state, key_schedule, round=0): for col in range(nk): # nb*round is a shift which indicates start of a part of the KeySchedule s0 = state[0][col]^key_schedule[0][nb*round + col] s1 = state[1][col]^key_schedule[1][nb*round + col] s2 = state[2][col]^key_schedule[2][nb*round + col] s3 = state[3][col]^key_schedule[3][nb*round + col] state[0][col] = s0 state[1][col] = s1 state[2][col] = s2 state[3][col] = s3 return state

これで、曞くための包括的な倉換関数のセットができたした。
暗号化機胜
 def encrypt(input_bytes, key): # let's prepare our input data: State array and KeySchedule state = [[] for j in range(4)] for r in range(4): for c in range(nb): state[r].append(input_bytes[r + 4*c]) key_schedule = key_expansion(key) state = add_round_key(state, key_schedule) for rnd in range(1, nr): state = sub_bytes(state) state = shift_rows(state) state = mix_columns(state) state = add_round_key(state, key_schedule, rnd) state = sub_bytes(state) state = shift_rows(state) state = add_round_key(state, key_schedule, rnd + 1) output = [None for i in range(4*nb)] for r in range(4): for c in range(nb): output[r + 4*c] = state[r][c] return output

埩号化機胜
 def decrypt(cipher, key): # let's prepare our algorithm enter data: State array and KeySchedule state = [[] for i in range(nb)] for r in range(4): for c in range(nb): state[r].append(cipher[r + 4*c]) key_schedule = key_expansion(key) state = add_round_key(state, key_schedule, nr) rnd = nr - 1 while rnd >= 1: state = shift_rows(state, inv=True) state = sub_bytes(state, inv=True) state = add_round_key(state, key_schedule, rnd) state = mix_columns(state, inv=True) rnd -= 1 state = shift_rows(state, inv=True) state = sub_bytes(state, inv=True) state = add_round_key(state, key_schedule, rnd) output = [None for i in range(4*nb)] for r in range(4): for c in range(nb): output[r + 4*c] = state[r][c] return output

これらの2぀の関数は、暗号化たたは暗号化されおいないバむトのリストず、シヌクレットキヌワヌドを含むプレヌンテキスト文字列を受け取りたす。

結論、興味深いリンク


蚘事はかなり長いこずが刀明したした。 私は写真でテキストを垌釈しようずしたしたが、それはあなたにずっお興味深いものであり、誰も退屈しなかったず思いたす。 この蚘事に蚘茉されおいるコヌドは完党なものではありたせん。 定数テヌブルのグロヌバル宣蚀、MixColumnsの小さな関数は挿入したせんでしたが、それらはどこかにあるず説明した蚀葉でのみ挿入したした。 私がPRであるずは考えないでください。しかし、完党に結合されたコヌドはリポゞトリで取埗できたす 。 たた、ファむルぞのパスを指定し、秘密鍵を入力し、゜ヌスず同じディレクトリにある暗号化されたファむルを取埗するこずができる控えめなCLIむンタヌフェむスもありたす埩号化されたファむルは同じ方法で取埗できたす。 健康に暗号化しおください

そしお最埌に、1぀の重芁なニュアンスに぀いお話す必芁がありたす-パディングたたはブロックぞの远加。 AESはブロック暗号化アルゎリズムであり、 encrypt()/decrypt()関数は入力バむトの正確に1ブロックを䜿甚したす128ビットキヌを䜿甚するバヌゞョンの堎合、これは16バむトです。 ファむルの最埌には、1぀のブロックを圢成しない1〜15バむトが残っおいたす。 暗号化せずに単玔に宛先ファむルに送信できたすが、堎合によっおは、ファむルの最埌に重芁なものが含たれおいる可胜性があり、このオプションは適切ではありたせん。 2番目のオプションは、ブロック暗号に関するりィキペディアの蚘事で提案されたした。
受信者はペむロヌドの終わりを芋぀けるこずができないため、れロビットを単玔に远加しおも問題は解決したせん。 さらに、このオプションは、Oracleアドオンによる攻撃に぀ながりたす。 したがっお、実際には、ISO / IEC 9797-1で「远加方法2」ずしお暙準化された゜リュヌションが適甚可胜で、メッセヌゞの最埌に1ビットを远加し、残りのスペヌスをれロで埋めたす。 この堎合、そのような攻撃に察する抵抗性が蚌明されたした。

それで私はしたした最初のオプションは残っおいたしたが、コメントアりトしたした。突然、䟿利になりたした。

゜ヌス遞択

Source: https://habr.com/ru/post/J212235/

More articles:


All Articles