【雑記】「サマーウォーズの暗号、ガチで解けるかやってみた」を C++ でやってみた

QuizKnock さんからネタをパクってきただけのクソ記事。

当記事の存在意義

まずはこの動画を見てください。

• サマーウォーズの暗号、ガチで解けるかやってみた【RSA暗号】 - YouTube

www.youtube.com

この動画でやっていたことを RSA のお勉強と頭の体操がてら
C++ で書いてみたというだけの記事です。

存在意義などありません。ごめんなさい。

問題と方針

第3問は素因数分解するだけなので省略。
第4, 5問は無理。

第1問

https://www.youtube.com/watch?v=kvC55N4k9ng

01, 02, ..., 26 を A, B, ..., Z に変換するという問題。

入力を std::string で受けて substr() で 2 桁ずつ取り出していくのがやりやすいかな。
ただ、数字をアルファベットに変換するときに、char 型の数字を int 型に変える

char c = '4';
int i = c - '0';
printf("%d\n", i);    // 4

的なノリで

int i = 4;
i--;
char c = 'A' + i;
printf("%c\n", c);    // D ?

とやってしまうのは重大な問題をはらみます。
というのも、数字の文字コードは連番になっていることが保証されているのに対し、
アルファベットの文字コードは必ずしもそうとは限らないからです。

例

• EBCDIC - Wikipedia

この問題を避けるには switch 等を使って 26 通りの分岐を作ればいいのですが、
ちょっとお遊びでやる分にはかなり面倒だったため、今回はこの辺を飲むことにしてこのノリでやってしまうことにしました。

何かそういうライブラリでもあるとは思うのですが、調べるのが怠くつらかったので止めました。
あまりにも非科学的な態度で申し訳ありません。。

いい方法を知っている方がいらっしゃいましたら教えてください。お願いします。

第2問

サマーウォーズの暗号、ガチで解けるかやってみた【RSA暗号】 - YouTube

疲れていてもはや考えることを放棄したので、 は から全探索させることに。
もっと早い方法があるかもしれないけどせいぜい で終わるから別にこれでもいいや。

の計算は 二分累乗法 の出番。

• 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

いわゆる modpow のテクニック。
今回の設定的には愚直にやっても ( なので ) そこまでかからなそうではあるけど、
自分が知ってることはどんどん使っていこう。子供か。

回答

可読性も統一性もないクソコードだけど、私が書いてて楽しければ問題ない。

• decode() は数字の文を std::string で受けてそれを英文に変換したものを std::string のまま返します。
• rsa() は文 を long long int 型で受けて計算結果の を long long int 型で返します。
  rsa() 内部で decode() まで含めてしまってもよかったかもしれない。

#include <iostream>

using ll = long long;
using namespace std;

// Convert 01, 02, ..., 26 into A, B, ..., Z
string decode(string str)
{
	int keta = str.length();
	keta /= 2;
	string ans;
	
	for(int i = 0; i < keta; i++) {
		string tmp = str.substr(2*i, 2);
		int tmp_n = stoi(tmp);
		tmp_n--;

		// A, B, ..., Z は連番になってるとは限らないので
		// これはあんまりよろしくない
		char res = 'A' + tmp_n;		
		ans += res;
	}
	return ans;
}

// Calculate a^n mod 
ll modpow(ll a, ll n, ll mod)
{
	ll res = 1;
	while(n > 0) {
		if(n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll rsa(ll p, ll q, ll e, ll c)
{
	ll n = p * q;
	ll m = 1;
	ll tmp;

	while(1) {
		tmp = m * (p - 1) * (q - 1);
		if((tmp + 1) % e == 0) break;
		m++;
	}
	ll d = (tmp + 1) / e;
	return modpow(c, d, n);
}

int main(int argc, char** argv)
{
	// Q.1
	string s = decode("23011819");
	cout << s << endl;

	// Q.2
	ll p = 37;
	ll q = 71;
	ll e = 79;
	ll c = 904;

	ll res = rsa(p, q, e, c);
	string ans = decode(to_string(res));
	cout << ans << endl;

	return 0;
}

これをコンパイルして実行すると

$ g++ rsa_qk.cpp -o a
$ ./a
WARS
OZ

ちゃんとできた。

めでたしめでたし。