ミニキャン言語 発展課題 '>=' '<=' を実装した
はじめに
せっかく発展課題が実装できたので記事にしました。
ミニキャンでは実装後スライド発表だったので、それも少し意識しました。
前提
GitHub - yamaguchi1024/mc-lang-3: セキュリティミニキャンプ2019山梨 MC言語講義 第三回事前課題
こちらの通常課題が全て終わっているのが前提です(発展課題に取り組むのでもちろんですが)
実装
まず全体ソースを載せておきます。先にソースが見てみたいという場合はこちらを
Tokenを使う
今回>=
と<=
は+
や<
となるべく近い実装にしたかったので、Tokenで実装しました。
追加した部分です。
lexer.h enum Token { ... tok_sle = -8, tok_sge = -9, }
codegen.h case tok_sle: L = Builder.CreateICmp(llvm::CmpInst::ICMP_SLE, L, R, "sletmp"); return Builder.CreateIntCast(L, Builder.getInt64Ty(), true, "cast_i1_to_i64"); case tok_sge: L = Builder.CreateICmp(llvm::CmpInst::ICMP_SGE, L, R, "sgetmp"); return Builder.CreateIntCast(L, Builder.getInt64Ty(), true, "cast_i1_to_i64");
mc.cpp BinopPrecedence[tok_sle] = 10; BinopPrecedence[tok_sge] = 10;
これで他の演算子と近い形で実装できるようになりました。
これに伴って変更しなければいけいない部分がparser.hにあります。
GetTokPrecedenceのif (!isascii(CurTok))
をif (!isascii(CurTok) && CurTok != tok_sle && CurTok != tok_sge)
に変更します。
+
や-
などの演算子はgettokでその演算子のasciiを返すのですが、>=
と<=
はtokenを返すのでisascii
でfalseになってしまいます。
だから条件を加えて-1をreturnしないようにします。
メイン処理
ここから実際に実装のための主な処理になります。
まずはソースを載せます。
if (lastChar == '>' || lastChar == '<') { tmpChar = lastChar; if (lastChar == '>') { lastChar = getNextChar(iFile); if (lastChar == '=') { tmpChar = tok_eof; lastChar = getNextChar(iFile); return tok_sge; } } if (lastChar == '<') { lastChar = getNextChar(iFile); if (lastChar == '=') { tmpChar = tok_eof; lastChar = getNextChar(iFile); return tok_sle; } } int tmp = lastChar; lastChar = tmpChar; tmpChar = tmp; }
今回実装する演算子は必ず>
か<
が先に来るのでそれを条件に分岐します。
その後にもう1文字読み込んでそれが=
ならtok_sgeかtok_sleをreturnします。
ここで一つ問題があって、読み込んだ文字が=
出なかった場合次の処理に影響が出てしまいます。
なのでそこを調整してあげなければいけません。説明のために次の処理を先に載せます。
if (tmpChar != tok_eof) { lastChar = tmpChar; } else { lastChar = getNextChar(iFile); }
私はgettokの処理の最後にこの処理を書きました。
tmpCharには初期値としてtok_eofを入れてあります。(ここは別になんでもよい)
tmpCharには>, <
の次の文字が保持されています。
tmpCharが初期値と異なる場合は次の文字が読まれているということなのでその値をlastCharに入れます。
もし次の文字を読んでいない場合は通常通り次の文字を読んで次の処理に移ります。
この分岐をすることによってトークンを先延ばしすることなく処理ができます。
以上、完成!
最後に
自分用メモと他人用の中間的な薄い内容になってしまったのは反省中です。
でも、ソースとこの記事でなんとなく>= , <=
実装の方向性は見えると思います。
実装方法はなかなかゴリ押しな部分があるので、ご指摘お待ちしております。
次は負の数辺りを実装しようと思います。
C++ Opencv 画像を合成する
最初に
今回は下の3つの画像を用いて、差分処理を行って画像を合成します。
青空の画像が背景で、Opencvのロゴが前景、真っ黒な画像がロゴを抜き取るための画像になります。
ソース
#include <iostream> #include <string> #include <sstream> #include <iomanip> #include <opencv2/opencv.hpp> /* img1とimg2の差分を返す */ cv::Mat frame_sub(cv::Mat& img1, cv::Mat& img2, int th = 20) { cv::Mat diff; cv::Mat mask; cv::absdiff(img1, img2, diff); cv::threshold(diff, mask, th, 255, cv::THRESH_BINARY); return mask; } /* 画像を合成する */ int image_composition(std::string base_path, std::string fg_path, std::string bg_path, std::string result_path, int x_pos = 0, int y_pos = 0, int th = 10) { // ベース画像の設定 cv::Mat base_frame; base_frame = cv::imread(base_path.c_str()); cv::cvtColor(base_frame, base_frame, cv::COLOR_BGR2GRAY); // 画像の読み込み cv::Mat bg = cv::imread(bg_path.c_str()); cv::Mat fg = cv::imread(fg_path.c_str()); // ROIがbg画像内に収まるように座標を調整 if (x_pos + fg.cols > bg.cols) { x_pos = bg.cols - fg.cols; } if (y_pos + fg.rows > bg.rows) { y_pos = bg.rows - fg.rows; } if (x_pos < 0 || y_pos < 0) return -1; // ROI(領域)の作成 cv::Rect rect_roi(x_pos, y_pos, fg.cols, fg.rows); cv::Mat roi = bg(rect_roi); cv::Mat fg_gray; cv::cvtColor(fg, fg_gray, cv::COLOR_BGR2GRAY); cv::Mat mask; mask = frame_sub(base_frame, fg_gray, th); cv::Mat mask_inv; cv::bitwise_not(mask, mask_inv); cv::Mat fg_down; cv::bitwise_and(roi, roi, fg_down, mask_inv); cv::add(fg, fg_down, roi); cv::imwrite(result_path.c_str(), bg); return 0; }
コード解説
今回二つの関数があるので、それぞれについて書いていきます。
frame_sub解説
関数が二つありますが、まずは上の処理のframe_subについて書きます。
cv::Mat frame_sub(cv::Mat& img1, cv::Mat& img2, int th = 20) { cv::Mat diff; cv::Mat mask; cv::absdiff(img1, img2, diff); cv::threshold(diff, mask, th, 255, cv::THRESH_BINARY); return mask; }
ここはimag1とimg2の画像の差分を返します。なので、今回はOpencvのロゴ画像を真っ黒画像の差分を得るために使います。
absdiffが実際に差分を取り出しているところです。取り出した差分がこれです。
これをmaskとして返したいのですが、このままだと色に違いがありマスクとして使えないのでさらに手を加えます。
cv::threshold(diff, mask, th, 255, cv::THRESH_BINARY);
ではdiffの画像を2値化、つまり白黒画像にしています。
THRESH_BINARY
は閾値(しきいち)を超えたらmaxValueにそれ以外は0にします。
今回閾値はth、maxValueは255になっているので、特に指定がない場合は20を超えるものは255,それ以外は0となり、白黒画像できます。
出力される画像はこれです。
mask画像が粗くなってしまうのは仕方がありません。
なので閾値を変更する、もしくは別の方法を使わないと綺麗な縁取りはできないと思います。多分。
(ここは私も悩んでいるところで、良い方法があれば教えてください。)
image_composition解説
ではこれで、maskを返却する関数の説明が終わったので、次はメインの処理に移りたいと思います。
cv::Mat base_frame; base_frame = cv::imread(base_path.c_str()); cv::cvtColor(base_frame, base_frame, cv::COLOR_BGR2GRAY); cv::Mat bg = cv::imread(bg_path.c_str()); cv::Mat fg = cv::imread(fg_path.c_str());
ここでは単純に処理に必要な画像を読み込んでいます。
それぞれimreadで画像を読み込んでいますが、引数がchar型なのでc_str()でstringからchar型へ変換しています。
base_frameだけcvtColorという処理を行っていますが、後の指定がCOLOR_BGR2GRAYなので、色付きのものをモノクロに変更している処理になります。
元々真っ黒だから意味がないように思えますが、チャンネルを揃えるために必要な処理になります。
RGBではないことに違和感を覚えますが、OpencvはBGRの順らしいです。
これはBGR2RGBでRGBに変更もできます。
if (x_pos + fg.cols > bg.cols) { x_pos = bg.cols - fg.cols; } if (y_pos + fg.rows > bg.rows) { y_pos = bg.rows - fg.rows; } if (x_pos < 0 || y_pos < 0) return -1;
ここの処理は引数で受け取った座標の修正を行っています。
今回合成にはROIという領域を前景のサイズ分確保して、そこに画像を合成するという処理を行います。
しかし、ROIの領域を確保する際に背景のサイズを超えてしまうとエラーになってしまうので座標を修正しています。
3つ目の条件分岐では前景画像の縦横幅どちらかが背景画像よりも大きくてもエラーになるので、その判定をしています。
cv::Rect rect_roi(x_pos, y_pos, fg.cols, fg.rows); cv::Mat roi = bg(rect_roi);
ROI, 画像を合成する領域の確保の処理がこれになります。
Rectクラスを用いて、左上座標と縦横幅を指定します。今回は前景画像のサイズに依存します。
指定した領域を背景から切り出してroiを確保します。
この際roiは値渡しではなく参照渡しになります。(割とミソ)
確保できた領域はこうなります。
今回座標は(0, 0)にしたので背景の左上から前景のサイズ分確保されています。
cv::Mat fg_gray; cv::cvtColor(fg, fg_gray, cv::COLOR_BGR2GRAY); cv::Mat mask; mask = frame_sub(base_frame, fg_gray, th);
ここでは前景画像をグレースケールに変換して、frame_subを行っています。
変換を行っているのはbase画像とチャンネルを揃えるためです。
チャンネルとは
- CV_8U 画像の場合,0 から 255
- CV_16U 画像の場合,0 から 65535
- CV_32F 画像の場合,0 から 1
というように決まっていて、これがずれると処理できないのでチャンネルを揃える必要があります。(結構めんどくさい)
さて本題からずれましたが元に戻ります。
この処理で確保できたmaskはframe_subで出力される画像です。
cv::Mat mask_inv; cv::bitwise_not(mask, mask_inv);
ここではmask画像をbitwise_notなので白黒を反転させています。
画像を見た方が早いと思います。
左側が反転した後の画像、mask_invです。右は通常のmaskになります。
cv::Mat fg_down; cv::bitwise_and(roi, roi, fg_down, mask_inv);
mask_invを使ってマスク処理を施してfg_downを作成します。
fg_downは前景の背景になります。言ってもわかりづらいので画像を載せます。
まあ、見たら何を言ってるのかわかったと思います。
勘の良い方はお気づきだと思いますが、ここまで来れば合成できたも同然です。
一応先にコードを載せます。
cv::add(fg, fg_down, roi);
前景画像にロゴの形がくり抜かれた画像を重ねているだけです。
ざっくりした説明ですが、イメージ付きやすいと思います。
一応ピクセル毎の合計を求める処理らしいです。
cv::imwrite(result_path.c_str(), bg);
最後にresult_pathで画像を書き出して終了です。
bgに処理を加えていないから出力は変わらないんじゃないか、と思いますが。
addした時の出力先がroiになっていて、roiはbgの領域を確保したものなのでroiを変更するとbgも変更されるという流れになっています。
なので、roiという別領域を画像情報として保持したのではなく、bg画像内での作業スペースを確保したというイメージの方がわかりやすいかと思います。
結果はこうなります。
まとめ
全体的な流れとしては
背景からroi(作業場所)を指定する
->roiに前景画像を貼り付ける
->roiに前景の背景を加える
->書き出して終了
という流れです。
間違った解釈が多い気がしますので、指摘していただけるとありがたいです。
pathの指定等が前回記事のimage_to_video等と違うのでpathがよーわからん、となったら以下を参照してください。
ここにmainを含めたコードを置いておくので参考にしてもらえればと思います。
p.s.
画像処理まだまだよくわからん!
C++ Opencv 静止画から動画を作成する
まずはソース
#include <iostream> #include <string> #include <sstream> #include <iomanip> #include <opencv2/opencv.hpp> int image_to_video(std::string result, std::string image_name, std::string ext, int frame_num, double frame_rate) { // {image_name}_00x.ext にするための桁数の取得 int digit = std::to_string(frame_num).length(); std::stringstream base; base << image_name << "_" << std::setw(digit) << std::setfill('0') << 0 << ext; cv::Mat Img = cv::imread(base.str().c_str()); int fourcc = cv::VideoWriter::fourcc('m', 'p', '4', 'v'); cv::VideoWriter writer(result, fourcc, frame_rate, cv::Size(Img.cols, Img.rows), true); for (int i = 0; i < frame_num; i++) { // {image_name}_00x.extの文字列作成 std::stringstream ss; ss << image_name << "_" << std::setw(digit) << std::setfill('0') << i << ext; std::cout << ss.str() << std::endl; // フレームを取得する Img = cv::imread(ss.str().c_str()); if (Img.empty()) { return -1; } // フレームの書き出し writer << Img; } return 0; }
関数解説
int digit = std::to_string(frame_num).length();
はimage_name_00x.jpgにするために、0埋めを何桁分するかというのを求めるための桁数の計算です。
フレーム数が10枚なら00.ext~, 100枚なら000.ext~になるように桁数を予め求めておきます。
std::stringstream base; base << image_name << "_" << std::setw(digit) << std::setfill('0') << 0 << ext; cv::Mat Img = cv::imread(base.str().c_str());
ここでは読み込むフレームの名前を求めています。
引数のimage_nameで、パスを含めて名前の番号の前までを指定しおきます。
例えばimage_000.jpg~image_999.jpgというフレームがあったとすると、ここの引数はimageになっています。
その名前に0埋めした番号とext 拡張子を追加して名前を生成しています。
ここではimage_name_0.jpgを求めています。理由はこの後。
int fourcc = cv::VideoWriter::fourcc('m', 'p', '4', 'v'); cv::VideoWriter writer(result, fourcc, frame_rate, cv::Size(Img.cols, Img.rows), true);
ここではVideoWriteクラスのインスタンスを生成しています。writerがインスタンス名になります。
fourccは生成する動画の拡張子で、指定はいくつかできるのですが今回はmp4限定でやっています。
Sizeで動画のサイズを決定できるのですが、ここではフレーム画像のサイズをそのまま動画のサイズにしています。
なので、先ほど1枚目のフレームを読み込んでいました。
1枚目のフレームをベース画像として、そのサイズに依存して動画を作成します。
最後のtrueはカラーか否かの設定ができます。
Img = cv::imread(ss.str().c_str());
あとはループで読み込む画像の名前を0~frame_numまで変化させつつ画像を読み込みます。
画像の読み込みはimreadを使うのですが、引数がchar型なので型変換を行います。
stringstreamからstring, stringからcharへこの1行では変換しています。
writer << Img;
最後に読み込んだ画像を動画へ追加していって、一つの動画を生成します。
ここでは読み込んだフレームを動画へ書き出しています。
まとめ
動画の書き出しは、静止画の書き出しの真逆なので、理解しやすかったです。
github.com メインも含めた関数の使用例をここに置いておくので、試しに動かしたい人はご利用ください。
C++ Opencv 動画から静止画を出力する
まずはソース
#include <iostream> #include <string> #include <sstream> #include <iomanip> #include <opencv2/opencv.hpp> int video_to_image(std::string result_image_name, std::string video_path, std::string ext) { cv::VideoCapture video(video_path); if (!video.isOpened()) { return -1; } int frame_num = video.get(cv::CAP_PROP_FRAME_COUNT); // {image_name}_00x.ext にするための桁数の取得 int digit = std::to_string(frame_num).length(); cv::Mat frame; int i; for (i = 0; i < frame_num; i++) { // フレームを取得する video >> frame; if (frame.empty()) { return -1; } // {image_name}_00x.extの文字列作成 std::stringstream ss; ss << result_image_name << "_" << std::setw(digit) << std::setfill('0') << i << ext; std::cout << ss.str() << std::endl; cv::imwrite(ss.str().c_str(), frame); } return i; }
関数解説
cv::VideoCapture video(video_path); if (!video.isOpened()) { return -1; }
この部分はVideoCaptureクラスのインスタンスを生成している部分です。
videoの部分がインスタンス名になり、動画情報を保持します。
video_pathは video.mp4
等をパスで指定してください。
video_pathが誤りの場合次の処理でreturn -1
します。
int frame_num = video.get(cv::CAP_PROP_FRAME_COUNT); // {image_name}_00x.ext にするための桁数の取得 int digit = std::to_string(frame_num).length();
この部分は少しだけ複雑(?)で保存する画像の名前に必要な情報を処理しています。
今回保存する動画の名前をhoge_000, hoge_001, ... , hoge999
のような感じにしたいと思っているので、そのためには動画には全部で何枚のフレームがあるかを確認しなければいけません。
そのためint frame_num = video.get(cv::CAP_PROP_FRAME_COUNT);
でフレームの数を取得しています。
その次の処理で10枚ならhoge_01, 100枚ならhoge_001 のような形にするためにフレーム数の桁数を計算しています。
cv::Mat frame; int i; for (i = 0; i < frame_num; i++) { // フレームを取得する video >> frame; if (frame.empty()) { return -1; } // {image_name}_00x.extの文字列作成 std::stringstream ss; ss << result_image_name << "_" << std::setw(digit) << std::setfill('0') << i << ext; std::cout << ss.str() << std::endl; cv::imwrite(ss.str().c_str(), frame); } return i;
cv::Mat
はopencvの画像情報を保持するクラスになります。
cv::Mat frame;
frameという名前のインスタンスを宣言しました。こ子に切り出していくフレーム情報を格納していきます。
切り出していく処理がvideo >> frame;
になります。
この処理でvideoに取り込んだ動画から1フレームを切り出してframeに格納しています。
std::stringstream ss; ss << result_image_name << "_" << std::setw(digit) << std::setfill('0') << i << ext;
ここの処理は保存する画像の名前を生成しています。
hoge_iという名前になるのですがsetwで桁数を指定してsetfillで0埋めをするという処理になります。
%03d
とかと同じ処理です。
cv::imwrite(ss.str().c_str(), frame);
ようやく書き出しです。
imwriteの引数がchar型なので変換しないといけないので、ss.str()でstring型へ、それをc_str()でchar型へ変換しています。
指定した名前でframeを書き出して終了です。
最後にカウンタiを返して、フレームの枚数を返却しています。
ここはframe_numを返しても同じです。
まとめ
解説というよりは自分用メモという感じです。
ここにメインを含めたプログラムの例を置いておきます。
「セキュリティミニキャンプ 2019 in 山梨 専門講座」に参加した話
セキュリティミニキャンプ 2019 in 山梨 に参加したので参加記を書こうと思います。
駄文ですがよろしくお願いします。
専門講座
現地到着してすぐにkaitoさんとエンカした。
専門講座2の方のUEFIのコードについて早速デバッグしてもらった。(ありがとうございます。)
オープニング
セキュリティキャンプ全国大会の紹介。
その後グループで軽い自己紹介を行いました。
専門講座1「ミニキャン言語を作ってみよう!」
この講義はメインが事前課題だったのでスライド発表を行いました。
スライド発表緊張しすぎて最後
「発表は以上です。ご静聴ありがとうございました。」
というべきところを
「発表ありがとうございました。」
と主催者側の締めの挨拶をしたのはここだけの内緒...
そんなことはさておき、どの参加者のスライド発表もとても見やすくまとめられていて、参考になりました。
後半の方達の発表は発展課題と独自開発などについての発表だったので自分とのレベルの差をひしひしと感じました。
自分は電卓っぽくプログラムの体裁を整えるという発表をしたのですが、その際に講師の高橋先生から
「今は'x+y'のような形式でしか値を取得していないから、より電卓っぽくするために'x+y+z+...'と指定できればい良いね」
というアドバイスをいただきました。
ありがとうございます。
本当にその通りで、今後はそこも含めて独自言語で全て実装することを目指そうと思います。
今回の講義はみなさんスライドのURLを貼ってくれていたので、再度振り返って勉強しようと思います。
そして最後に一つ気になったこと。
高橋先生が着ていたLLVMドラゴンのTシャツはどこから出ているものなのだろう。
専門講座2「OSの力を借りずに起動するアプリを作ろう」
この講義では軽く講師の内田先生の紹介があった後、C言語ポインタクイズをしました。
クイズを通して以前よりポインタの理解が深まったと思います。
アセンブリ側からのアプローチでポインタを理解するのは初めてだったのでそれが理解を深めた要因だと思いました。
クイズ終了後は内田先生が作成しているMikanOSのデモを見せていただきました。
もうOSじゃん。という印象でした。
「自作OSは凄さがあまり伝わらないところが面白い」
といった感じのことのおっしゃっていて(曖昧)、面白いなと思いましたw
そのあとはオプションの話題としてUSBドライバとABIについて講義をしていただきました。
個人的には「もっと詳しい内田の自己紹介」という項目に惹かれたのですが勇気が出ませんでした。(少し後悔している(おい))
講義の中でjavaのメモリ境界線の話になったのですが、javaは8バイトの倍数でオブジェクトのメモリを確保するらしい。そのため下位アドレスを記憶しておく必要がなくなってより多くのアドレス空間を識別できる。
というお話でした。(多分)
講義が終わったあとは黙々と演習をする時間でした。
バシバシ質問しようと思っていたのですが、理解している部分が少なすぎて質問をまとめることもできていませんでした。
これはかなりの反省点で、もっと課題をやり込んで質問がまとまっている状態で講義に参加するのがベストだったなと思いました。
次に活かそうと思います。
まあそういったひどい状況だったのですが、チューターの方には自分の詰まっている部分を言語化するところから手伝っていただき一つ一つ丁寧に教えていただきました。
ありがとうございます。
しかし、演習の時間内で発展課題は終わりませんでした。
終わってからも撮影隊で来ていた方やチューターの方にお時間をいただきデバッグに協力していただきました。
バス・電車のギリギリまでお話させていただけたので温かみを感じました。
アロケーションしたアドレスとプログラムを展開したアドレスがずれている(かと思われた)問題があり、hexdumpなどを使ってアドレスを確認し、再計算してあげる必要があるという話でした。
まあ後日談なのですが、ミスはかなり初歩的なミスで、実際には
status = fs->Read(fs, &read_byte, (void *)elf_file_addr);
としなければいけない部分を
status = fs->Read(fs, &read_byte, &elf_file_addr);
としてしまっていたという初歩的なミスでした。
こんな単純なミス、逆にプロの方は気づきにくいなと思いました。(時間もない中で、かつアドレスに焦点を当てていたので)
申し訳なさでいっぱいです。チューターの方申し訳ございませんでした。
専門講座が終わって
専門講座は一瞬で終わってしまいました。
講師の方やチューターの方ともあまりお話ができなかったのも残念でした。こういうところでの積極性は絶対持っておくべきだと感じました。
事前課題が大ボリュームだったが故、より短く感じました。
物足りない感を感じた人が周りにいらっしゃったので僕を含めて、5人で近くのサイゼリヤで進捗を出す会をしました。
私はそこでTaskerさんにお力を貸していただき、発展課題を完了させました。(ありがとうございます)
自分以外みんな強い人で完全に置いてかれていました。
が、とても楽しい空間でした。良い刺激でした。
まとめ
今回の専門講座を通して、自分の積み上げのなさを再確認しました。
他の強い方は例外なくきちんと積み上げたものがあって、熱中して語るものがあって。という感じでしたが自分はそれがなく不甲斐なかったです。
次会うまでにはきちんと積み上げて、一つ何か熱く語れるものを持っておこうと思います。
最後に
濃密な3週間&2日間でとても刺激を受けました。
セキュリティ・ミニキャンプ 2019 in 山梨
本当にありがとうございました。
バーナム暗号
バーナム暗号とは
バーナム暗号はバーナム(Vernam)さんによって考案された共通鍵暗号になります。この暗号はシャノンによって理論的に解読不可能であることが証明されており、高い秘匿性を備えています。
バーナム暗号の長所
バーナム暗号の最大の長所といえばその安全性の高さだと思います。バーナム暗号がなぜ非常に高い安全性を持っているのか。また、解読不可能とはどういうことなのかは、暗号の仕組みを書いた後にまた書こうと思います。
バーナム暗号には他にも処理速度が高速であるという長所もあります。これも仕組みをみていただければわかるのですが、とてもシンプルなため処理が高速に行えるようになっています。
バーナム暗号の短所
バーナム暗号の短所は何と言っても鍵にあります。バーナム暗号は平文と同サイズの秘密鍵を用いらなければなりません。大きな平文をやり取りする場合をそれ相応の鍵が必要です。また、鍵もランダムなものでなくてはならないので、生成だけでも真性乱数を用いるとなるととても手間がかかります。さらに、バーナム暗号の秘密鍵は使い捨てになるので暗号化のたびに使用可能な秘密鍵が減っていくという短所があります。4ビットの平文をやり取りしたら16回しか暗号化が行えないということになります。
短所はまだあって、鍵の配送も大きな問題となっています。共通鍵暗号なのであらかじめ相手と秘密鍵を共有しておかなければなりません。秘密鍵は他の人に知られてはいけないので安全に配送するにはどうするのかという問題点があります。そもそも秘密鍵が安全に配送できるなら平文を配送できるのではないか。というジレンマ?もあります。
バーナム暗号の仕組み
まず前提として平文をm、秘密鍵をkey、暗号文をcとしておきます。
仕組みは簡単でnビットの平文mとnビットの秘密鍵keyの排他的論理和をとるだけです。式は
c = m ⊕ key
となります。上記の式が暗号化になります。
復号は今度暗号文cと秘密鍵keyとのXORをとるだけです。式は
m = c ⊕ key
となります。
正当性の検証
排他的論理和の特性を活かした正当性の検証というものがあります。
これは同一の値のXORは0になるのを利用したものです。
例 1111 ⊕ 1111 = 0000 や 1010 ⊕ 1010 = 0000
正当性の検証の式としてはこんな感じになります。(暗号技術の全て参照)
Dec(key, Enc(key, m)) = Dec(key, m⊕key) = m ⊕ key ⊕ key = m ⊕ 0 = m
Decは復号、Encは暗号化を表しています。
Encは暗号化なのでm⊕keyとなります。DecはEncとkeyのXORなのでm⊕key⊕keyとなります。同一の値は0になるのでkeyとkeyは打ち消しあって0になります。0とのXORはそのまま値が出てくるのでmが残ります。
実践
実際に暗号化、復号、そして正当性の検証までを行いたいと思います。
問題:m = 1010, key = 0011とした場合の上記3つを求める。
まず暗号化
c = m ⊕ key c = 1010 ⊕ 0011 c = 1001
続いて復号
m = c ⊕ key m = 1001 ⊕ 0011 m = 1010
元の平文に戻りました。
最後に正当性の検証
Dec(key, Enc(key, m)) = Dec(key, m ⊕ key) = Dec(key, 1001) = Dec(0011, 1001) = 0011 ⊕ 1001 m = 1010
平文mに戻ったので正当性があるということになります。
バーナム暗号がなぜ安全なのか
バーナム暗号はシャノンによって解読不可能ということが証明されていると冒頭に書きました。これは鍵を総当たりで調べることができない、というような計算的なものではありません。仮に鍵を全て総当たりで調べることができても解読できないということです。ポイントとしては、推測はできても解読はできないという点が挙げられます。
攻撃者が総当たりで鍵候補と暗号文とのXORをとり復号しようとしてもそれが正しい平文なのか判断できません。これがバーナム暗号が安全であり解読不能であるという理由です。
どういうことかというと
例えば平文mが”A"という文字だった場合。AをASCIIコードでやり取りするとします。Aは0x41なので0100 0001bとなります。
これに対する秘密鍵の候補は同サイズのものなので範囲とすると
0000 0000 ~ 1111 1111になります。
これらの範囲でXORをとって暗号文cをいくら復号しようとしても結果はただ全ビット候補とのXORになりますので、AだけでなくBやCも結果として出てきます。結果、攻撃者は復号結果が正しいものか判断できないので解読不可能となります。
そしてここで先ほどの正当性の検証が少し出てきます。
正当性の検証にはkeyとmの二つの要素が出てきました。つまり平文が正しいか判断するには少なくとも秘密鍵keyを知っておく必要があります。しかし攻撃側は盗んだ暗号文しか知らないので正当性を検証できず攻撃失敗となります。
keyをいくら推測しても、そこから得られた結果は推測に過ぎないので、復号できたとは言えないのです。
pythonを用いた単一換字式暗号の実装
換字式暗号とは
平文を1文字あるいは複数文字に対し、別の文字・記号を割り当て変換することで暗号文を作り出す方式。
A⇆B B⇆D の場合、ABという平文はBDとなる。
実装
今回はpythonを用いて実装しました。文字の扱いはpythonの方が楽だと思ったのもあって、勉強&リハビリも兼ねて選びました。
では、コードです。
sigma = {'a':'@', 'b':'V', 'c':'4', 'd':'B', 'e':'*', 'f':'$', 'g':'(', 'h':'A', 'i':'J', 'j':'W', 'k':'O', 'l':']','m':'!', 'n':'-', 'o':'+', 'p':'~', 'q':'^', 'r':'=', 's':'?', 't':'%', 'u':'H', 'v':'R', 'w':'Y', 'x':'C', 'y':'M', 'z':'T'} def encryption(m): c = [sigma[a] for a in m] return c def decryption(c): m = [] for a in c: for key, value in sigma.items(): if value == a: m.append(key) break else: m.append('?') return m if __name__=='__main__': print('暗号化(0) 復号(1) >> ', end='') f = int(input()) print('文字列 >> ', end='') s = input() if f==1: c = decryption(s) else: c = encryption(s) print(''.join(c))
アルファベットに対し、記号や文字(テキトーに選びました)を辞書を用いて設定しました。
復号に関しては、割り当てのない値が来た時に「?」を代わりに表示するようにしてあります。
実行結果になります。
1・2枚目は暗号化と復号です。3枚目も復号ですが、「a」に対応する「@」を「"」に変えてあります。
「"」に対応するキーはないので、復号できず「?」を表示してあります。
おわりに
単一換字式暗号は対応表を仲間内で共有しておく必要があるので、そこの管理は大変だと思いましたがそこさえクリアできれば転置式よりは安全だと思いました。
暗号技術のすべてでは、アルファベットに対しアルファベット(Aに対しDなど)を割り当てていましたが、記号を使うとより暗号感が出るなと思い少しアレンジを加えてみました。
引き続き暗号技術の勉強を頑張ります。
p.s.
python久々すぎて、簡単なプログラムでも結構時間かかりました。
あと作法が全くわからなかったので、汚コードだと思いますがご了承ください。