転置式暗号の実装
転置式暗号とは
平文の文字を入れ替えて作る暗号化の方法のことです。一番目と二番目の文字を入れ替える。三番目と四番目の文字を入れ替える、など様々な転置の法則で暗号文を作ります。
実装
今回は文字列を abcdefg の場合 abcd efg というように4文字単位で区切って、以下の方式で転置しようと思います。
1番目→3番目 2番目→1番目 3番目→4番目 4番目→2番目
それで、実装したコードがこれです。
#include <stdio.h> #include <string.h> #include <ctype.h> int tau[][4] = {{1,2,3,4}, {3,1,4,2}}; void transposition(char str[]) { int i, j; int main, sub; char tmp; char len4[4]; printf("暗号化(0) 復号(1) >> "); scanf("%d", &main); printf("文字列>"); scanf("%s", str); if (main) { sub = 0; for (i = 0; i < strlen(str); i++) { str[i] = tolower(str[i]); } } else { sub = 1; for (i = 0; i < strlen(str); i++) { str[i] = toupper(str[i]); } } for (i = 0; i < strlen(str)/4; i++) { for (j = 0; j < 4; j++) { len4[j] = str[i*4+j]; } for (j = 0; j < 4; j++) { str[i*4+tau[main][j]-1] = len4[tau[sub][j]-1]; } } } int main(void) { char str[256]; transposition(str); printf("%s\n", str); return 0; }
tauという二次元配列を作っておいて、暗号化と復号に対応できるようにしました。
4文字区切りにして、あまりが0でなかった場合の処理は、文字数に対応した転置を行なうかパディングするかなどがあるのですが、今回はそのまま表示することにしました。
実行結果を載せます。
ということで転置式暗号の暗号化と復号の結果になります。
両方ともうまくいってると思います。
おわりに
転置式は必ず平文の文字が使われるので、換字式と比べると弱いのかな?と思いました。
勉強したてなので、まだわかりませんが...
p.s.
画像サイズがいつも大きくてすいません。
やる気のあるときにサイズ小さくします。
シーザー暗号の実装
はじめに
暗号技術のすべてという本を購入しました。
そこでシーザー暗号が出てきたので改めて実装してみることにしました。
シーザー暗号とは
シーザー暗号とは、アルファベットの先頭文字を指定したROT分だけずらす暗号方式のことです。
ABCのROT1なら、BCDとなります。ずらした結果がZを超えてしまった場合はAに戻ります。
ちなみにアルファベットは26文字なのでROT13だと二回暗号化を行うと実質復号になるという性質も持ちます。(Aの13文字ずらしはNであり、Nの13文字ずらしはAだからです)
では、実装したコードを載せます
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #define CASELEN 26 char case_u[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; char case_l[] = "abcdefghijklmnopqrstuvwxyz"; int str_check(char character) { for (int i = 0; i < CASELEN; i++) { if (character == case_u[i]) return 1; } return 0; } void encryption(char str[], int length, int rot) { for (int i = 0; i < length; i++) { str[i] = toupper(str[i]); } for (int i = 0; i < length; i++) { if (str_check(str[i])) { printf("%c", case_u[(str[i]-'A'+rot)%CASELEN]); } else { printf("%c", str[i]); } } } int main(void) { char str[256]; int rot; printf("文字列>"); fgets(str, sizeof str, stdin); printf("ROT >"); scanf("%d", &rot); encryption(str, strlen(str), rot); return 0; }
str_check関数はアルファベットなのかそれ以外(記号や数字)なのかを判定する関数です。
それを用いてencryption関数ではアルファベットなら文字をずらして表示し、そうでないならそのまま表示するようにします。
暗号的には、空白もピリオドも暗号化した方が良いのでしょうが、今回は結果がわかりやすいことを重視してこの実装にしました。
scanfで空白文字が入力できないのを忘れていて少し焦ったのですがfgetsを使うことで実装できました。
ということで、実行結果を示します。
ROT13なので2回の実行で元どおりになりました。
おわりに
シーザー暗号は理解しやすい暗号なので初学者の私でもとても面白かったです。
暗号技術のすべてには、まだまだ色々な暗号方式が載っているみたいなのでインプット頑張ろうと思います。
理解できた範囲でアウトプットも行なっていこうと思います。
総当たり攻撃を実験した話
/etc/shadowでパスワードが見られると組み合わせによっては一瞬でパスワードがバレてしまうらしい。
ということで、pythonのcryptモジュールを用いて総当たり攻撃を実践してみる。
useradd target passwd target
今回はあらかじめ上記のコマンドでtargetというユーザーをKali Linux上に追加しておきました。
/etc/shadowの一番下にtargetユーザーが追加されていました。
target:$6$PjN7BsaQ$7LgY2it/svbRqEDV1PXQDilWdiUtSA26JRK1Ej3Mhmjggrtn0Z2P2w8zWdY0ZiLM4Y2hi/WK7.oi7CHkxL0kf/:17920:0:99999:7:::
ユーザー名:ハッシュ値という形で表記されています。
今回使うpythonのcrypt関数の使い方はこんな感じ。
crypt.crypt("パスワード", "ソルト")
linuxの場合前半の$6$PjN7BsaQ$がソルトになっているのでここを使います。
ここはアカウントによってもちろん異なりますが、$x$xxxx$という形は同じです。
戻り値がハッシュ値になるので、あとはタイトルにある通りパスワードの部分を総当たりで攻撃し、/etc/shadowのtargetのハッシュ値と比べるだけです。
ちなみに今回は実験なので数字のみ4文字という設定で行います。
用意したpythonのプログラムはこんな感じです。
import crypt import sys def main(): number="1234567890" hash_value="$6$PjN7BsaQ$7LgY2it/svbRqEDV1PXQDilWdiUtSA26JRK1Ej3Mhmjggrtn0Z2P2w8zWdY0ZiLM4Y2hi/WK7.oi7CHkxL0kf/" salt = "$6$PjN7BsaQ$" for num1 in number: for num2 in number: for num3 in number: for num4 in number: src = num1 + num2 + num3 + num4 print(src) dst = crypt.crypt(src, salt) if hash_value == dst: print("Password is " + src) sys.exit() if __name__=="__main__": main()
1111 / 1112 / 1113 という形でパスワードを端から生成し、 cryptで利用します。
あとはtargetのパスワードのハッシュ値hash_valueと同じハッシュ値ができたらそれがパスワードです。
実行結果を貼ります。
こんな感じでパスワードがわかります。
もし、他のユーザーのパスワードがわからなくなってもこれで安心??
参照局所性
参照局所性とは
プログラムがアクセスするアドレスは一部あるいは特定の箇所に集中する。これを参照局所性という。
参照局所性は「空間的参照局所性」と「時間的参照局所性」の2種類に分けられる。
これだけではよくわからないので、それぞれを下にまとめてみます。
空間的参照局所性
空間的参照局所性とは、一度アクセスされたアドレスに近いアドレスは他に比べアクセスされる可能性が高いということです。
これはどういうことかというのを雑に作った図を用いて説明しようと思います。
図1
色合いが気持ち悪いのはスルーでお願いします。
ABCDと書かれている塊がメモリで、AやBはアドレスだと思ってください。
アドレスCにアクセスしていると仮定すると、水色に塗られた部分がCですがその前後がアクセスされやすいよ。ということが空間的参照局所性があるということになります。今回でしたら緑色に塗られた部分が対象になります。
言われてみると確かにそうかもという感じですね。
図2
こういうAという配列があった時に、使用しているのがA(0)なら次に使用する可能性が高いのはA(1)ですよね。
もちろんA(2)やA(4)を使うこともありますが、可能性が高いと言われたらA(1)です。
これをメモリに当てはめて考えれば空間的参照局所性も少しわかりやすいのかなと思います。
(まあ配列もメモリに塊で確保されますしね...(間違ってたらすいません))
時間的参照局所性
一度アクセスしたアドレスは再度アクセスされる可能性が高い。
まあ、これはそのままなので特に説明はないです。
関数なんかも作ったのであれば何回も使うと思いますし、そういうことだと思います。
まとめ
この参照局所性がメモリアレイ構成に繋がってきます。
また機会があればメモリアレイも勉強してまとめてみたいです。
他のアーキテクチャも同様。
pingコマンド
pingとは
pingはターゲットのホストが存在しているかを調べることができる仕組みで、ネットワーク障害を調べる時などに利用される。
pingはICMPプロトコルを利用して実装されている。ターゲットにICMPのEcho Request(type 8)を送り、Echo Reply(type 0)が返ってくると到達成功となり、ターゲットホストが存在しているということになる。しかし、今は設定によって電源が入っていてもpingを受け取らない(返事をしない)ホストもあるためpingが到達しないからホストが存在していないというわけではない。
pingのやり取りを見る
実際にICMPを用いてやり取りをしているのかをwiresharkを利用して調べる。
以下のコマンドを実行してその流れを見ていく。
ping -c 1 172.217.25.195 ※-cオプションはpingを送る回数を決めるもので今回は1回だけ送る。 172.217.25.195はgoogle.co.jpのIPアドレス
送ったパケットをwiresharkでキャプチャする。
送ったパケットを見るとまず画面上部からICMPを用いてEcho Requestを送っていることががわかる。
その1行下を見ると172.217.25.195からEcho replyが返ってきている。
画像下の方を見るとICMPの内容を見ることができる。青ラインのところを見ると、Echo requestがType 8であることも確認できる。
返ってきたパケットについても見てみる。
Type 0 でEcho replyがきていることが確認できる。
Checksumまで確認できてテンションが上がる。
基本正規表現について
今回「新しいLinuxの教科書」という名著で正規表現を勉強したので、アウトプットしようと思います。
まず
yeah year yeahh yeahhh yeahyeah yeahyeahyeah
というテキストファイルがあったとします。
[year]と[year]という単語を抽出したいときに、使うのが「.(ドット)」です。
「.(ドット)」は任意の1文字にマッチするメタ文字です。
'yea.'
なので、上記のようにすると[yeah]や[year]はもちろん[yead][yeaa]などにもマッチします。
しかし、「.(ドット)」のある部分は最後の1文字なので[yerh]や[yeeh]にはヒットしませんし、[yeahh]にもヒットしません。
では、[yeahh]や[yeahhh]にマッチさせるにはどうしたら良いかというと、「*(アスタリスク)」を使います。
「*」は0回以上の繰り返しにマッチします。例えば
'yea.*'
とすると[yeah]や[yeahh],[yeahhh]にマッチします。また、0回以上なので[yea]にもマッチします。
また、間に「.」を入れて[yeah][yeeah]にマッチさせることも可能です。
さらに、特定の文字を指定することもできます。
しかし今までの場合だと[yeah][yead]や[yea!]にもマッチしてしまいます。
そうではなく、[yeah]と[year]のみにマッチさせたい場合は
(1) 'yea[hr]' (2) 'yea[^hr]'
(1)とすることで、最後が h か r の単語のみをマッチさせることができます。
また(2)のようにすると h と r 以外の文字を最後に使っている単語をマッチさせることができます。
あとは、[yeahh]にはマッチさせたいんだけど[yeahhh]にはマッチさせたくない。
[yeah]と[yeahh]にはマッチさせたいんだけど[yeahhh]にはマッチさせたくない。
など細かな指定もすることができます。
(1) '\{m,n\}' (2) '\{m\}' (3) '\{m,\}
まず、(1)のようにするとm回以上n回以下の繰り返しにマッチさせることができます。
なので、[yeah]と[yeahh]だけにマッチさせたかったら'yeah\{1,2\}'とするとマッチさせることができます。
(2)の場合はちょうどm回繰り返しの単語のみマッチできます。
'yeah\{2\}'とすると[yeah]にはマッチせず、[yeahh]にのみマッチします。
最後(3)はm回以上の繰り返しにマッチします。
'yeah\{3,\}'とすると[yeahhh]や[yeahhhh]にマッチします。
[yeah]や[yeahh]にはマッチしません。
次に行頭、行末指定について書こうと思います。
今までの通りやっていくと[yeah]にマッチしているけど[yeahh]までマッチした対象として出てきてしまう。といったことがあると思います。
それは[yeahh]の"yeah"の部分にマッチしているためです。
なので[yeahyeah]などにもマッチしてしまいます。
そこで指定するのが行頭/行末です。
(1) 'yeah$' (2) '^yeah'
「^」は行頭を『$」は行末を意味します。
なので(1)の場合は、 [yeah]で終わるもののみにマッチします。[yeah]はもちろん、[ayeah]や[yeahyeah]などにマッチします。
(2)の方は逆に行頭を意味します。
[yeah]で始まるもの、[yeahh]や[yeahh]、もしくは[yeahyeah]にもマッチします。
しかし、行頭指定なので[aayeah]など先頭に[yeah]以外の文字が入るものにはマッチしません。
最後に [yeahyeah]はいいけど[yeahyeahyeah]は嫌なんだ、という指定にも正規表現は応えてくれるという事を紹介して終わろうと思います。
(1) '\(\)' (2)'\(yeah\)' (3)'^\(yeah\)\{2\}$'
例題文を(3) にまとめておきました。
(1)は基本的な構成です。
(2)のように(1)に当てはめる事でyeahを グループ化 しています。
グループ化することにより、全体に対して繰り返し等の指定をすることができます。
(3)はこの記事の総まとめみたいな例文です。
読み解いていくと
行頭から始まり「^」グループ化「\(\)」した[yeah]を
2回ちょうど繰り返していて「\{2\}」、その後行末である。
これで[yeahyeah]のみにマッチする文になりました。
今回はこれでまとめを終わろうと思います。
基本正規表現の基本的な扱い方についてまとめました。
拡張正規表現という便利なものもあるので、機会(モチベーション)があればまた、まとめようと思います。
最後になりますが、正規表現は色々な書き方があって出来上がったものだけ見るととても難しいですが、一から勉強して、読み解いていくととても面白いものなのでこれからも自分自身勉強していこうと思います。
皆さんも色々なパターンを試して楽しんでください。
また、プロの方々、ミス や ここ違うんじゃないの? といったことがあればコメントやツイッターで指摘/アドバイスください。
お願いします。
strcmpを使った条件分岐
2つの文字列をstrcmpを使って比較し、同じ文字列なら中の処理をするというコードを書くとこうなります
if(!strcmp(str1, str2)) { hoge }
なぜstrcmpの前に!をつけなければいけないのかをこの記事では書いていこうと思います。
strcmpは2つの文字列を比べ
- str1 == str2 なら0
- str1 > str2 なら1
- str1 < str2 なら-1
を返す関数です
ここで大事なのが同じ場合に0を返すというところです。
if文ではFalseは0, Trueは1で判断しているのでstrcmpで同じ文字列だった場合0が返ってきて判定はFalseになります。
str1とstr2が同じ文字列だった場合のイメージは
if(0) { hoge }
こういった感じです
!strcmpとすることで!は否定なので
同じ場合はTrue
違う場合はFalse
を返してくれるようになります
一応if(-1)でもTrue判定になるようなので、str1 < str2 でもFalseを返してくれます。
strcmpを使った条件分岐ではTrueとFalseがわかりづらいということを記事にしてみました。
矛盾していた点や理解の仕方がおかしな部分などありましたら、ご指摘ください