後輩にシーザー暗号を解けたと伝えたら、「アフィン暗号やってください」と言われた。一生懸命頑張ったので、書く。
問題文/暗号文
1 |
WCVD WVTX NFP CZIX DPLXXEXE WF SKXZH ZQQVMX LVYCXK |
アフィン暗号とは
難しい説明文しかウェブに掲載されていなかったので、簡単に書く。ただしずぶの素人なので、確実さは保証できない。間違いだらけかもしれない。
暗号とか全く習っていない人間なので、基礎的な部分が完全に抜け落ちてるかもしれない。まぁ、そういう人間の視点の記事もあっても良いだろうと思う。
アルファベットの文字列を暗号化するとして、ある特定のアルファベット(例、A)をほかの特定のアルファベット(例、Z)に変換する。そして、そのあとに特定の文字数だけずらす。という暗号化方法。
平文:HELLO
→HをAに変換。EをBに変換。LをCに変換。OをDに変換
ABCCD→三文字ずつずらす
暗号文:DEFFG
→なんか自分で書いていて、もやっとしている。あまり例えが適切でない。上記のようにプログラムを書くのだけど、解釈としては間違っている気がする。(文章を)削除しようか悩んだが、このまま掲載。
アフィン暗号の解き方・考え方
さっぱりわからない。webでヒントを探す。古典暗号 – アフィン暗号が参考になった。
アフィン暗号
Enc(x):=ax+b mod p
シーザー暗号
Enc(x):=x+b mod p
ここで、xは平文, a, b,pはパラメータを表す
(アルファベットの場合、bの値は1~26の間。pは26)
ということは、大雑把に考えると、アフィン暗号は、シーザー暗号にaをかければ良い。
ある特定のアルファベットをある特定のアルファベットに変換するということは、最大でもaの値は26(アルファベットは全部で26文字なので)。
シーザー暗号はbが1~26までの全26通りだったが、それにa=1~26をそれぞれ掛け合わせる。全、26×26通りとなる。その中で意味の通る文が正解って感じ?
シーザー暗号はVBで作成したので、アフィン暗号は(殆ど変わらないけど)今勉強中のVBAで作成してみる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
Sub affine() Dim InputMoji As String Dim MojiNumber As Integer Dim MojiInfo As String Dim MojiAsc As Integer Dim MojiString As String InputMoji = Range("A1").Value MojiNumber = Len(InputMoji) For h = 0 To 25 For j = 0 To 25 For i = 1 To MojiNumber MojiInfo = Mid(InputMoji, i, 1) MojiAsc = Asc(MojiInfo) '計算をするため、A=0~Z=25の値にする' MojiAsc = MojiAsc - 65 MojiAsc = MojiAsc * h + j If MojiAsc >= 26 Then MojiAsc = MojiAsc Mod 26 End If 'アスキーに戻す' MojiAsc = MojiAsc + 65 MojiString = MojiString + Chr(MojiAsc) MojiAsc = 0 Next Debug.Print MojiString, MojiString = vbCrLf Next Next End Sub |
…一応それっぽい文字列が出てきたんだけど、うまく行かない。大体の流れは合ってそうなんだけど、確実にどっかが違う。
これ以上考えてもわからないので、後輩に教えてもらう。
どうやら上記のコードは暗号文作成の考え方みたいだ。うーむ。
y=ax+b mod 26でaの値が1~26、bの値も1~26で全パターンの中で正解が出そうな気がするんだけど…。
→解決。Debug.Print
でイミデイトウィンドウに出力していたが、イミデイトウィンドウの最大出力行は200行までのようだ。全パターン表示だと、26*26=676通りになる。全パターンでも正解がでるけど、あまりスマートじゃないので、↓へ。
教わったことを書き出す。
シーザー暗号はy=x+bという形。(yは暗号文、xは平文)変形させると
x=y-b
なので単純にb=1~26の値を足し合わせる(引く)ことで復号化出来る。
が、アフィン暗号はまずaの値を出さないと復号化出来ない。
上述したコードは、aの値が1~26のときの、暗号文作成のソースコードだということになる。
アフィン暗号
Encryption(暗号化)
y=ax+b mod p
Decryption(解読)
※平文xについて解く
x=a-1(y-b) mod p
なので、a-1を求める必要がある。
そして、aの値の最大値は25。また、pと互いに素であることが条件(pの値は26)。なぜなら、互いに素でないと割り切れてしまい、同じ文字で堂々巡りするだけだから。
よってaの値は(互いに素である)12個(1,3,5,7,9,11,15,17,19,21,23,25)。
a-1の求め方。
a=3のときを例に考える。
まあ単純に考えるとa=3ならば、a-1は「1/3」となる。でも「1/3 mod 26」とはどういうこと?となる。
「1/3」は「3と掛け算すると答えが1となる数字」と考える。それを逆数と呼ぶ。
「mod26したときに1となる、3の逆数」を求める。
3 × 1 = 3
3 mod 26 = 3
3 × 2 = 6
6 mod 26 = 6
3 × 3 = 9
9 mod 26 = 9
…
..
.
3 × 9 = 27
27 mod 26 = 1
計算していくと、9だったときに、mod 26をすると1になることがわかった。
よって (a=3/mod26) のときの a-1 は 9 になる。
1~pまでをaにかけて(modした値が)最初に1になった数字がa-1
これを「aのmodインバース」と呼ぶ
とのこと。modインバースのくだりが、わかったようなわからないような…。自分で調べて補完する。
参考になったサイト→3 ÷ 4 ≡ 9 mod 11を計算するのに必要なモジュラ逆数を理解する
試行錯誤の末、完成
完成したコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
Sub affineCipher() 'modインバースを計算。互いに素となる、26までの数字(12個)の逆数を配列data(12)へ格納する' Dim gyakusuu As Integer Dim data(12) data(1) = 1 data(2) = 3 data(3) = 5 data(4) = 7 data(5) = 9 data(6) = 11 data(7) = 15 data(8) = 17 data(9) = 19 data(10) = 21 data(11) = 22 data(12) = 23 For a = 1 To 12 For p = 1 To 26 gyakusuu = data(a) * p Mod 26 If gyakusuu = 1 Then data(a) = p GoTo Continue End If Next Continue: Next Dim InputMoji As String Dim MojiNumber As Integer Dim MojiInfo As String Dim MojiAsc As Integer Dim MojiString As String 'A1セルの暗号文を変数へ格納' InputMoji = Range("A1").Value '暗号文の文字数を取得' MojiNumber = Len(InputMoji) For a = 1 To 12 For b = 1 To 25 '文字数分だけ繰り返し処理' For i = 1 To MojiNumber '1文字ずつ取得' MojiInfo = Mid(InputMoji, i, 1) '文字列をアスキーコードへ変換' MojiAsc = asc(MojiInfo) 'スペースを除外(アスキー32)' If MojiAsc = 32 Then GoTo ExceptSpace End If '計算をするため、A=0~Z=25の値にする' MojiAsc = MojiAsc - 65 'y=a^-1(y-b) mod 26の形' MojiAsc = (MojiAsc * data(a) - b) Mod 26 'アスキーに戻す' MojiAsc = MojiAsc + 65 'スペース(アスキーコード32)の場合は、処理しない' ExceptSpace: 'アスキーコードを文字列に戻して、1文字から文章にする' MojiString = MojiString + Chr(MojiAsc) MojiAsc = 0 Next 'イミデイトウィンドウへ出力' '→他で出力したかったが、改行がうまく行かない。とりあえずこれで' '13*25=325通りあるけど、答えでたから...。後ほど追記修正。' Debug.Print MojiString, MojiString = vbCrLf Next Next End Sub |
指摘を受けて修正
後輩にコードを見せたら、かなりアドバイスもらった。「初心者が頑張って書いたんだなぁ」ってコードらしい。…その通りだけど…。
まず改善点としては、変数の名前をわかりやすくすること。
自分でプログラムしているからわかるのであって、他の人が見たら「この変数なんだ?」となる。他の人だけでなく、後から自分が見返してもわからなくなる。
なので「変数は何を意味するか」をひと目見てわかるように名前をつけることが大切。そのためには変数の名前が多少冗長になったとしても構わない。
→基本的に変数名は英語で統一しようかな。
参考:新人プログラマが絶対に知っておきたい、日本語変数利用時の作法
InputMoji→意味がわからない。暗号文を表す→cipherTxt
MojiNumber→意味がわからない。暗号文の長さを表す→cipherTxtLength
MojiString→意味がわからない。答えを表す→answer
・変数の頭文字は小文字にする。大文字を使用するのは定数(値が変動しないもの。決まっているもの。)
・data(a)に新たな値が代入されている。もともとの変数とは違う用途に使われている。わかりづらい。新たな変数にする。
・配列(0)を使わないと、怒られるらしい。うーむ。
先頭が0番。要素数が x個の場合、配列の最後の要素はx-1となる(VBAだとxも使用できる?)。言語によって異なるので、気をつける。
配列(12)は要素数が12個。配列(12)には値が格納できない(場合もある)。
…直感的にわかりづらいから苦手なのだけど、配列(0)を使用することに慣れておいたほうが良いか。
・必要のない変数は使用しない。わかりづらくなる
Asc(Mid(...
でよい
・あと、GOTO文は可読性が良くないので、なるべくなら使用しない方が良いとのこと。while文などで置き換えることが可能なので、次回から気をつけたい。
改良したコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
Sub AffineCipherImprovement() 'modインバースを計算。互いに素となる、26までの数字(12個)の逆数を配列reciprocal(12)へ格納する' Dim reciprocalJudge As Integer Dim reciprocal(12) As Integer Dim data(12) As Integer data(0) = 1 data(1) = 3 data(2) = 5 data(3) = 7 data(4) = 9 data(5) = 11 data(6) = 15 data(7) = 17 data(8) = 19 data(9) = 21 data(10) = 22 data(11) = 23 For a = 0 To 11 For i = 1 To 26 '1~26までを掛けて、mod26する。' reciprocalJudge = data(a) * i Mod 26 '逆数が1のとき、配列に格納。そして、残りの処理をスキップして、次のループへ。' If reciprocalJudge = 1 Then reciprocal(a) = i GoTo CONTINUE End If Next CONTINUE: Next Dim cipherTxt As String Dim cipherTxtLength As Integer Dim cipherTxtAsc As Integer Dim answer As String 'A1セルの暗号文を変数へ格納' cipherTxt = Range("A1").Value '暗号文の文字数を取得' cipherTxtLength = Len(cipherTxt) For a = 0 To 11 For b = 1 To 25 '文字数分だけ繰り返し処理' For i = 1 To cipherTxtLength '1文字ずつ取得し、文字列をアスキーコードへ変換' cipherTxtAsc = asc(Mid(cipherTxt, i, 1)) 'スペースを除外(アスキー32)' If cipherTxtAsc = 32 Then GoTo EXCEPTSPACE End If '計算をするため、A=0~Z=25の値にする' cipherTxtAsc = cipherTxtAsc - 65 'y=a^-1(y-b) mod 26の形' cipherTxtAsc = (cipherTxtAsc * reciprocal(a) - b) Mod 26 'アスキーに戻す' cipherTxtAsc = cipherTxtAsc + 65 'スペース(アスキーコード32)の場合は、処理しない' EXCEPTSPACE: 'アスキーコードを文字列に戻して、文章へ' answer = answer + Chr(cipherTxtAsc) cipherTxtAsc = 0 Next 'イミデイトウィンドウへ出力' '他の方法で出力したかったが、改行がうまく行かない。とりあえずこれで' '12*25=300通りあるけど、答えでたから...。後ほど追記修正したい' Debug.Print answer, answer = vbCrLf Next Next End Sub |
…けっこう頑張ったけど、わかりやすくなったのか?
自分じゃ全然気づかないことだから、指摘してもらうととてもありがたい。不出来なものを公開するのは恥ずかしいけど、同じような初心者の人の参考になったら良いなぁ…なんて思っている。
親身な指導で実力をつけるプログラミングスクール | CodeVillage