C++を学び始めたので、C++の環境構築をやったついでにRSA暗号についてGPT先生に教えてもらおうと思い、勉強してみました。ほぼGPT先生に質問するだけという手法でやってます。
RSA暗号は公開鍵暗号システムの一つで、1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンによって提案されました。RSAの名称も彼らの頭文字から取られています。この暗号システムは、公開鍵と秘密鍵のペアを使用し、一方の鍵で暗号化した情報をもう一方の鍵でのみ復号することができるという特性があります。
RSA暗号は次のような数学的原理に基づいています。
YouTubeに分かりやすい解説があったので置いておきます。
GPT先生にRSA暗号をまずC++で書いてもらい、わからないところをすべて質問してわかるまで続けました。
#include <iostream>
#include <cmath>
#include <random>
#include <utility>
#include <limits>
#include <string> // Include for std::string and std::getline
#include <vector>
// Euclidean algorithm to find the greatest common divisor
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// Function to find modular exponentiation
int modExp(int base, int exp, int mod) {
int result = 1;
while (exp > 0) {
if (exp % 2 == 1) // If exp is odd, multiply base with result
result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Generate RSA keys
std::pair<std::pair<int, int>, std::pair<int, int>> generateKeys() {
int p = 61; // First prime number
int q = 53; // Second prime number
int n = p * q;
int phi = (p - 1) * (q - 1);
int e;
std::random_device rd;
std::mt19937 gen(rd());
do {
std::uniform_int_distribution<> dis(2, phi - 1);
e = dis(gen);
} while (gcd(e, phi) != 1);
int d = 1;
while ((d * e) % phi != 1) {
d++;
}
return { {e, n}, {d, n} };
}
// Encrypt using the public key
int encrypt(int plaintext, int e, int n) {
return modExp(plaintext, e, n);
}
// Decrypt using the private key
int decrypt(int ciphertext, int d, int n) {
return modExp(ciphertext, d, n);
}
int main() {
auto keys = generateKeys();
int e = keys.first.first, n = keys.first.second;
int d = keys.second.first;
std::string input;
std::cout << "Enter a string to encrypt: ";
std::getline(std::cin, input); // Use std::getline to read a line of text
std::vector<int> encrypted;
std::cout << "Encrypted data: ";
for (char c : input) {
int enc = encrypt(c, e, n);
encrypted.push_back(enc);
std::cout << enc << " ";
}
std::cout << std::endl;
std::cout << "Do you want to decrypt the data? (y/n): ";
char response;
std::cin >> response;
if (response == 'y' || response == 'Y') {
std::string decrypted;
for (int num : encrypted) {
decrypted.push_back(static_cast<char>(decrypt(num, d, n)));
}
std::cout << "Decrypted string: " << decrypted << std::endl;
}
else {
std::cout << "Decryption skipped." << std::endl;
}
return 0;
}
実行結果
Enter a string to encrypt: hello
Encrypted data: 1019 406 2426 2426 3039
Do you want to decrypt the data? (y/n): y
Decrypted string: hello
分からないところをGPT先生に聞いてみました。
ここでASCII値に対してRSA暗号化を施しているのならEncrypted Dataは文字列の長さの分だけ増えていくと思ったのでテストしてみました。
Enter a string to encrypt: o
Encrypted data: 1048
Do you want to decrypt the data? (y/n): y
Decrypted string: o
Enter a string to encrypt: on
Encrypted data: 233 2001
Do you want to decrypt the data? (y/n): y
Decrypted string: on
Enter a string to encrypt: one
Encrypted data: 1453 2550 1992
Do you want to decrypt the data? (y/n): y
Decrypted string: one
Enter a string to encrypt: one
Encrypted data: 1048 1387 1920 1241
Do you want to decrypt the data? (y/n): y
Decrypted string: one
Enter a string to encrypt: one letter
Encrypted data: 3161 3191 284 2106 840 284 2325 2325 284 1131
Do you want to decrypt the data? (y/n): y
Decrypted string: one letter
予想通り、1文字につき4つの数字で表示されています。
ここまででざっくりですが、RSA暗号の仕組みを「体験」として理解できました。まだC++を習得してるといえる段階にいないので標準的な使い方すらもわからず、文法がわからないのか関数がわからないのかも曖昧なレベルなので、一旦RSA暗号の理解はここで止めて再度C++の学習に戻ります。
以下のかわいらしい本で学習しています。
