Last active
January 5, 2022 16:45
-
-
Save jerryc05/1887e3f15b90241ccd9b7c574f7cb1f4 to your computer and use it in GitHub Desktop.
Stupid EECS 376 RSA Calculator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <array> | |
| #include <cassert> | |
| #include <ctgmath> | |
| #include <iostream> | |
| #include <vector> | |
| #define PHI "\u03C6" | |
| #define MUL "\u00D7" | |
| static constexpr | |
| bool isPrime(const intmax_t x) noexcept { | |
| if (x <= 7919) { | |
| switch (x) { | |
| case 2: case 3: case 5: case 7: case 11: case 13: case 17: case 19: case 23: case 29: case 31: case 37: case 41: case 43: case 47: case 53: case 59: case 61: case 67: case 71: case 73: case 79: case 83: case 89: case 97: case 101: case 103: case 107: case 109: case 113: case 127: case 131: case 137: case 139: case 149: case 151: case 157: case 163: case 167: case 173: case 179: case 181: case 191: case 193: case 197: case 199: case 211: case 223: case 227: case 229: case 233: case 239: case 241: case 251: case 257: case 263: case 269: case 271: case 277: case 281: case 283: case 293: case 307: case 311: case 313: case 317: case 331: case 337: case 347: case 349: case 353: case 359: case 367: case 373: case 379: case 383: case 389: case 397: case 401: case 409: case 419: case 421: case 431: case 433: case 439: case 443: case 449: case 457: case 461: case 463: case 467: case 479: case 487: case 491: case 499: case 503: case 509: case 521: case 523: case 541: case 547: case 557: case 563: case 569: case 571: case 577: case 587: case 593: case 599: case 601: case 607: case 613: case 617: case 619: case 631: case 641: case 643: case 647: case 653: case 659: case 661: case 673: case 677: case 683: case 691: case 701: case 709: case 719: case 727: case 733: case 739: case 743: case 751: case 757: case 761: case 769: case 773: case 787: case 797: case 809: case 811: case 821: case 823: case 827: case 829: case 839: case 853: case 857: case 859: case 863: case 877: case 881: case 883: case 887: case 907: case 911: case 919: case 929: case 937: case 941: case 947: case 953: case 967: case 971: case 977: case 983: case 991: case 997: case 1009: case 1013: case 1019: case 1021: case 1031: case 1033: case 1039: case 1049: case 1051: case 1061: case 1063: case 1069: case 1087: case 1091: case 1093: case 1097: case 1103: case 1109: case 1117: case 1123: case 1129: case 1151: case 1153: case 1163: case 1171: case 1181: case 1187: case 1193: case 1201: case 1213: case 1217: case 1223: case 1229: case 1231: case 1237: case 1249: case 1259: case 1277: case 1279: case 1283: case 1289: case 1291: case 1297: case 1301: case 1303: case 1307: case 1319: case 1321: case 1327: case 1361: case 1367: case 1373: case 1381: case 1399: case 1409: case 1423: case 1427: case 1429: case 1433: case 1439: case 1447: case 1451: case 1453: case 1459: case 1471: case 1481: case 1483: case 1487: case 1489: case 1493: case 1499: case 1511: case 1523: case 1531: case 1543: case 1549: case 1553: case 1559: case 1567: case 1571: case 1579: case 1583: case 1597: case 1601: case 1607: case 1609: case 1613: case 1619: case 1621: case 1627: case 1637: case 1657: case 1663: case 1667: case 1669: case 1693: case 1697: case 1699: case 1709: case 1721: case 1723: case 1733: case 1741: case 1747: case 1753: case 1759: case 1777: case 1783: case 1787: case 1789: case 1801: case 1811: case 1823: case 1831: case 1847: case 1861: case 1867: case 1871: case 1873: case 1877: case 1879: case 1889: case 1901: case 1907: case 1913: case 1931: case 1933: case 1949: case 1951: case 1973: case 1979: case 1987: case 1993: case 1997: case 1999: case 2003: case 2011: case 2017: case 2027: case 2029: case 2039: case 2053: case 2063: case 2069: case 2081: case 2083: case 2087: case 2089: case 2099: case 2111: case 2113: case 2129: case 2131: case 2137: case 2141: case 2143: case 2153: case 2161: case 2179: case 2203: case 2207: case 2213: case 2221: case 2237: case 2239: case 2243: case 2251: case 2267: case 2269: case 2273: case 2281: case 2287: case 2293: case 2297: case 2309: case 2311: case 2333: case 2339: case 2341: case 2347: case 2351: case 2357: case 2371: case 2377: case 2381: case 2383: case 2389: case 2393: case 2399: case 2411: case 2417: case 2423: case 2437: case 2441: case 2447: case 2459: case 2467: case 2473: case 2477: case 2503: case 2521: case 2531: case 2539: case 2543: case 2549: case 2551: case 2557: case 2579: case 2591: case 2593: case 2609: case 2617: case 2621: case 2633: case 2647: case 2657: case 2659: case 2663: case 2671: case 2677: case 2683: case 2687: case 2689: case 2693: case 2699: case 2707: case 2711: case 2713: case 2719: case 2729: case 2731: case 2741: case 2749: case 2753: case 2767: case 2777: case 2789: case 2791: case 2797: case 2801: case 2803: case 2819: case 2833: case 2837: case 2843: case 2851: case 2857: case 2861: case 2879: case 2887: case 2897: case 2903: case 2909: case 2917: case 2927: case 2939: case 2953: case 2957: case 2963: case 2969: case 2971: case 2999: case 3001: case 3011: case 3019: case 3023: case 3037: case 3041: case 3049: case 3061: case 3067: case 3079: case 3083: case 3089: case 3109: case 3119: case 3121: case 3137: case 3163: case 3167: case 3169: case 3181: case 3187: case 3191: case 3203: case 3209: case 3217: case 3221: case 3229: case 3251: case 3253: case 3257: case 3259: case 3271: case 3299: case 3301: case 3307: case 3313: case 3319: case 3323: case 3329: case 3331: case 3343: case 3347: case 3359: case 3361: case 3371: case 3373: case 3389: case 3391: case 3407: case 3413: case 3433: case 3449: case 3457: case 3461: case 3463: case 3467: case 3469: case 3491: case 3499: case 3511: case 3517: case 3527: case 3529: case 3533: case 3539: case 3541: case 3547: case 3557: case 3559: case 3571: case 3581: case 3583: case 3593: case 3607: case 3613: case 3617: case 3623: case 3631: case 3637: case 3643: case 3659: case 3671: case 3673: case 3677: case 3691: case 3697: case 3701: case 3709: case 3719: case 3727: case 3733: case 3739: case 3761: case 3767: case 3769: case 3779: case 3793: case 3797: case 3803: case 3821: case 3823: case 3833: case 3847: case 3851: case 3853: case 3863: case 3877: case 3881: case 3889: case 3907: case 3911: case 3917: case 3919: case 3923: case 3929: case 3931: case 3943: case 3947: case 3967: case 3989: case 4001: case 4003: case 4007: case 4013: case 4019: case 4021: case 4027: case 4049: case 4051: case 4057: case 4073: case 4079: case 4091: case 4093: case 4099: case 4111: case 4127: case 4129: case 4133: case 4139: case 4153: case 4157: case 4159: case 4177: case 4201: case 4211: case 4217: case 4219: case 4229: case 4231: case 4241: case 4243: case 4253: case 4259: case 4261: case 4271: case 4273: case 4283: case 4289: case 4297: case 4327: case 4337: case 4339: case 4349: case 4357: case 4363: case 4373: case 4391: case 4397: case 4409: case 4421: case 4423: case 4441: case 4447: case 4451: case 4457: case 4463: case 4481: case 4483: case 4493: case 4507: case 4513: case 4517: case 4519: case 4523: case 4547: case 4549: case 4561: case 4567: case 4583: case 4591: case 4597: case 4603: case 4621: case 4637: case 4639: case 4643: case 4649: case 4651: case 4657: case 4663: case 4673: case 4679: case 4691: case 4703: case 4721: case 4723: case 4729: case 4733: case 4751: case 4759: case 4783: case 4787: case 4789: case 4793: case 4799: case 4801: case 4813: case 4817: case 4831: case 4861: case 4871: case 4877: case 4889: case 4903: case 4909: case 4919: case 4931: case 4933: case 4937: case 4943: case 4951: case 4957: case 4967: case 4969: case 4973: case 4987: case 4993: case 4999: case 5003: case 5009: case 5011: case 5021: case 5023: case 5039: case 5051: case 5059: case 5077: case 5081: case 5087: case 5099: case 5101: case 5107: case 5113: case 5119: case 5147: case 5153: case 5167: case 5171: case 5179: case 5189: case 5197: case 5209: case 5227: case 5231: case 5233: case 5237: case 5261: case 5273: case 5279: case 5281: case 5297: case 5303: case 5309: case 5323: case 5333: case 5347: case 5351: case 5381: case 5387: case 5393: case 5399: case 5407: case 5413: case 5417: case 5419: case 5431: case 5437: case 5441: case 5443: case 5449: case 5471: case 5477: case 5479: case 5483: case 5501: case 5503: case 5507: case 5519: case 5521: case 5527: case 5531: case 5557: case 5563: case 5569: case 5573: case 5581: case 5591: case 5623: case 5639: case 5641: case 5647: case 5651: case 5653: case 5657: case 5659: case 5669: case 5683: case 5689: case 5693: case 5701: case 5711: case 5717: case 5737: case 5741: case 5743: case 5749: case 5779: case 5783: case 5791: case 5801: case 5807: case 5813: case 5821: case 5827: case 5839: case 5843: case 5849: case 5851: case 5857: case 5861: case 5867: case 5869: case 5879: case 5881: case 5897: case 5903: case 5923: case 5927: case 5939: case 5953: case 5981: case 5987: case 6007: case 6011: case 6029: case 6037: case 6043: case 6047: case 6053: case 6067: case 6073: case 6079: case 6089: case 6091: case 6101: case 6113: case 6121: case 6131: case 6133: case 6143: case 6151: case 6163: case 6173: case 6197: case 6199: case 6203: case 6211: case 6217: case 6221: case 6229: case 6247: case 6257: case 6263: case 6269: case 6271: case 6277: case 6287: case 6299: case 6301: case 6311: case 6317: case 6323: case 6329: case 6337: case 6343: case 6353: case 6359: case 6361: case 6367: case 6373: case 6379: case 6389: case 6397: case 6421: case 6427: case 6449: case 6451: case 6469: case 6473: case 6481: case 6491: case 6521: case 6529: case 6547: case 6551: case 6553: case 6563: case 6569: case 6571: case 6577: case 6581: case 6599: case 6607: case 6619: case 6637: case 6653: case 6659: case 6661: case 6673: case 6679: case 6689: case 6691: case 6701: case 6703: case 6709: case 6719: case 6733: case 6737: case 6761: case 6763: case 6779: case 6781: case 6791: case 6793: case 6803: case 6823: case 6827: case 6829: case 6833: case 6841: case 6857: case 6863: case 6869: case 6871: case 6883: case 6899: case 6907: case 6911: case 6917: case 6947: case 6949: case 6959: case 6961: case 6967: case 6971: case 6977: case 6983: case 6991: case 6997: case 7001: case 7013: case 7019: case 7027: case 7039: case 7043: case 7057: case 7069: case 7079: case 7103: case 7109: case 7121: case 7127: case 7129: case 7151: case 7159: case 7177: case 7187: case 7193: case 7207: case 7211: case 7213: case 7219: case 7229: case 7237: case 7243: case 7247: case 7253: case 7283: case 7297: case 7307: case 7309: case 7321: case 7331: case 7333: case 7349: case 7351: case 7369: case 7393: case 7411: case 7417: case 7433: case 7451: case 7457: case 7459: case 7477: case 7481: case 7487: case 7489: case 7499: case 7507: case 7517: case 7523: case 7529: case 7537: case 7541: case 7547: case 7549: case 7559: case 7561: case 7573: case 7577: case 7583: case 7589: case 7591: case 7603: case 7607: case 7621: case 7639: case 7643: case 7649: case 7669: case 7673: case 7681: case 7687: case 7691: case 7699: case 7703: case 7717: case 7723: case 7727: case 7741: case 7753: case 7757: case 7759: case 7789: case 7793: case 7817: case 7823: case 7829: case 7841: case 7853: case 7867: case 7873: case 7877: case 7879: case 7883: case 7901: case 7907: case 7919: | |
| return true; | |
| default: | |
| return false; | |
| } | |
| } | |
| const auto sqrtX = static_cast<intmax_t>(std::sqrt(x)); | |
| for (intmax_t i = 3; i <= sqrtX; i += 2) { | |
| if (x % i == 0) { return false; } | |
| } | |
| return true; | |
| } | |
| static constexpr | |
| intmax_t iPowMod(intmax_t base, intmax_t exp, | |
| const intmax_t mod = -1, bool print = false) noexcept { | |
| const auto &printModNl = [&]() { | |
| if (mod != -1) { | |
| std::cout << " mod " << mod; | |
| } | |
| std::cout << '\n'; | |
| }; | |
| if (print) { | |
| std::cout << "Rule 0: a^(p-1) mod p = 1, when a and p satisfy Fermat's Little Thm.\n" | |
| "Rule 1: a^b mod c = (a^2 mod c)^( b/2) mod c, when b is even.\n" | |
| "Rule 2: a^b mod c = a" MUL "(a^2 mod c)^((b-1)/2) mod c, when b is odd.\n\n" | |
| " " << base << '^' << exp; | |
| printModNl(); | |
| } | |
| if (mod != -1 && base >= mod) { | |
| if (print) { | |
| std::cout << "= (" << base << " mod " << mod << ")^" << exp << " mod " << mod << '\n'; | |
| } | |
| base %= mod; | |
| if (print) { | |
| std::cout << "= " << base << '^' << exp; | |
| printModNl(); | |
| } | |
| } | |
| if (isPrime(mod)) { | |
| const auto &q = exp / (mod - 1); | |
| const auto &r = exp % (mod - 1); | |
| if (print) { | |
| std::cout << "\nAccording to Fermat's Little Thm, since [modulo=" | |
| << mod << "] is prime,\n " | |
| << base << '^' << exp << " mod " << mod << '\n' | |
| << "= " << base << "^(" << mod - 1 << MUL << q << ") " MUL " " | |
| << base << '^' << r << " mod " << mod << '\n' | |
| << "= 1^" << q << " " MUL " " << base << '^' << r << " mod " << mod << "\n\n"; | |
| } | |
| exp = r; | |
| } | |
| intmax_t result = 1; | |
| for (;;) { | |
| if (exp & 1) { | |
| if (print) { std::cout << "= (" << result << MUL << base << " mod " << mod << ")" MUL; } | |
| result *= base; | |
| if (mod != -1) { result %= mod; } | |
| } else { | |
| if (print) { std::cout << "= " << result << MUL; } | |
| } | |
| if ((exp >> 1) == 0) { | |
| if (print) { | |
| std::cout << base << "^(" << exp << "/2) mod " << mod | |
| << " = " << result << "\n\n"; | |
| } | |
| return result; | |
| } | |
| if (print) { std::cout << '(' << base << "^2 mod " << mod << ")^(" << exp << "/2)"; } | |
| exp >>= 1; | |
| base *= base; | |
| if (mod != -1) { base %= mod; } | |
| if (print) { | |
| std::cout << " mod " << mod << ' ' | |
| << "= " << result << MUL << base << '^' << exp; | |
| printModNl(); | |
| } | |
| } | |
| } | |
| static | |
| bool modGenerator(intmax_t mod, intmax_t g) { | |
| std::vector<bool> vec(static_cast<size_t>(mod), false); | |
| for (intmax_t i = 1; i < mod; ++i) { | |
| const auto &result = static_cast<size_t>(iPowMod(g, i, mod)); | |
| std::cout << g << '^' << i << " mod " << mod << " = " << result << '\n'; | |
| if (vec[result]) { | |
| std::cout << '\n'; | |
| return false; | |
| } else { | |
| vec[result] = true; | |
| } | |
| } | |
| std::cout << '\n'; | |
| return true; | |
| } | |
| static | |
| auto gcdExt(intmax_t x, intmax_t y) { | |
| if (x < y) { std::swap(x, y); } | |
| struct Gcd { | |
| intmax_t x_, y_, q_, r_; | |
| Gcd(intmax_t x, intmax_t y, intmax_t q, intmax_t r) | |
| : x_{x}, y_{y}, q_{q}, r_{r} {} | |
| }; | |
| std::vector<Gcd> gcdVec{{x, y, x / y, x % y}}; | |
| // GCD procedure | |
| { | |
| for (;;) { | |
| x = gcdVec.back().y_; | |
| y = gcdVec.back().r_; | |
| if (y > 1) { | |
| gcdVec.emplace_back(x, y, x / y, x % y); | |
| } else { | |
| gcdVec.emplace_back(x, y, static_cast<intmax_t>(-1), static_cast<intmax_t>(-1)); | |
| break; | |
| } | |
| } | |
| assert(gcdVec.back().y_ == 0 || gcdVec.back().y_ == 1); | |
| } | |
| // Print GCD procedure | |
| { | |
| std::cout << "GCD procedure:\n| x \t| y \t| q \t| r\n|---\t|---\t|---\t|---\n"; | |
| for (auto &v : gcdVec) { | |
| std::cout << '|' << v.x_ << " \t|" << v.y_ << " \t|"; | |
| if (v.q_ != static_cast<intmax_t>(-1)) { | |
| std::cout << v.q_; | |
| } else { | |
| std::cout << "---"; | |
| } | |
| std::cout << " \t|"; | |
| if (v.r_ != static_cast<intmax_t>(-1)) { | |
| std::cout << v.r_; | |
| } else { | |
| std::cout << "---"; | |
| } | |
| std::cout << '\n'; | |
| } | |
| std::cout << '\n'; | |
| } | |
| struct { | |
| intmax_t gcd; | |
| intmax_t cX, cY; | |
| } result{.gcd=gcdVec.back().y_ == 0 ? gcdVec.back().x_ : 1, .cX=1}; | |
| std::cout << "GCD result: [" << result.gcd << "].\n\n"; | |
| // GCDExt procedure | |
| { | |
| auto idx = gcdVec.size() - 1; | |
| while (gcdVec[idx].r_ != result.gcd && idx--) {} | |
| result.cY = static_cast<intmax_t>(-gcdVec[idx].q_); | |
| std::cout << "GCDExt procedure:\n| a \t| b\n|---\t|---\n| " | |
| << result.cX << " \t| " << result.cY << '\n'; | |
| for (; idx--;) { | |
| const auto cXBackup = static_cast<intmax_t>(result.cX); | |
| result.cX = static_cast<intmax_t>(result.cY); | |
| result.cY = cXBackup - result.cX * static_cast<intmax_t>(gcdVec[idx].q_); | |
| std::cout << "| " << result.cX << " \t| " | |
| << cXBackup << " - (" << result.cX << ")*" | |
| << static_cast<intmax_t>(gcdVec[idx].q_) | |
| << " = " << result.cY << '\n'; | |
| } | |
| std::cout << '\n'; | |
| } | |
| assert(result.cX * gcdVec.front().x_ + result.cY * gcdVec.front().y_ == result.gcd); | |
| std::cout << "Verify: a" MUL "x+b" MUL "y = (" | |
| << result.cX << ")" MUL << gcdVec.front().x_ << " + (" | |
| << result.cY << ")" MUL << gcdVec.front().y_ << " = " | |
| << result.cX * gcdVec.front().x_ + result.cY * gcdVec.front().y_ | |
| << "\n\n"; | |
| return result; | |
| } | |
| static | |
| auto factorPrime(intmax_t n) noexcept { | |
| intmax_t p, q; | |
| const auto sqrtN = static_cast<intmax_t>(std::sqrt(n)); | |
| for (p = 2; p <= sqrtN; ++p) { | |
| if (n % p == 0) { break; } | |
| } | |
| if (p > sqrtN) { | |
| std::cerr << "ERR: Cannot find p of [n=" << n << "].\n"; | |
| exit(1); | |
| } | |
| q = n / p; | |
| static const auto &checkPrime = [&](intmax_t x) { | |
| if (!isPrime(x)) { | |
| std::cerr << "ERR: [" << x << "], as a factor of [n=" << n << "], is not a prime.\n"; | |
| exit(1); | |
| } | |
| }; | |
| checkPrime(p); | |
| checkPrime(q); | |
| std::cout << "Found two primes [p=" << p << "], [q=" << q | |
| << "] s.t. p" MUL "q = [n=" << n << "].\n\n"; | |
| struct { | |
| intmax_t p, q; | |
| } result{p, q}; | |
| return result; | |
| } | |
| intmax_t getAnotherKey(intmax_t phi, intmax_t key) { | |
| const auto &gcdResult = [&]() { | |
| const auto &gcdResultX = gcdExt(phi, key); | |
| if (gcdResultX.gcd != 1) { | |
| std::cerr << "ERR: GCD of [" PHI "(n)=" << phi << "] and [key=" << key << "] is [" | |
| << gcdResultX.gcd << "], which is not [1].\n"; | |
| exit(1); | |
| } | |
| return gcdResultX; | |
| }(); | |
| assert (gcdResult.cX * phi + gcdResult.cY * key == gcdResult.gcd | |
| || gcdResult.cY * phi + gcdResult.cX * key == gcdResult.gcd); | |
| return (((gcdResult.cX * phi + gcdResult.cY * key == gcdResult.gcd) | |
| ? gcdResult.cY : gcdResult.cX) + phi) % phi; | |
| } | |
| struct Rsa { | |
| intmax_t n_, e_, d_; | |
| static | |
| const Rsa ne(const intmax_t n, const intmax_t e) { | |
| Rsa rsa{.e_=e}; | |
| // find p, q | |
| const auto &factorResult = factorPrime(n); | |
| rsa.n_ = factorResult.p * factorResult.q; | |
| const auto &phi = (factorResult.p - 1) * (factorResult.q - 1); | |
| // find e | |
| rsa.d_ = getAnotherKey(phi, e); | |
| std::cout << "Found the private key, the inverse of [e=" << e | |
| << "] in mod [" PHI "(n)=" PHI "(" << n << ")=" << phi | |
| << "]: [d=" << rsa.d_ << "].\n"; | |
| return rsa; | |
| } | |
| static | |
| const Rsa nd(const intmax_t n, const intmax_t d) { | |
| Rsa rsa{.d_=d}; | |
| // find p, q | |
| const auto &factorResult = factorPrime(n); | |
| rsa.n_ = factorResult.p * factorResult.q; | |
| const auto &phi = (factorResult.p - 1) * (factorResult.q - 1); | |
| // find e | |
| rsa.e_ = getAnotherKey(phi, d); | |
| std::cout << "Found the private key, the inverse of [d=" << d | |
| << "] in mod [" PHI "(n)=" PHI "(" << n << ")=" << phi | |
| << "]: [e=" << rsa.e_ << "].\n"; | |
| return rsa; | |
| } | |
| intmax_t c(intmax_t m) const noexcept { | |
| assert(m >= 0); | |
| assert(e_ >= 0); | |
| assert(n_ >= 0); | |
| return iPowMod(m, e_, n_); | |
| } | |
| intmax_t decrypt(intmax_t c) const noexcept { | |
| assert(c >= 0); | |
| assert(d_ >= 0); | |
| assert(n_ >= 0); | |
| return iPowMod(c, d_, n_); | |
| } | |
| void verifyDecrypt(intmax_t c, intmax_t m = static_cast<intmax_t>(-1)) const noexcept { | |
| assert(n_ > 0); | |
| std::cout << "Verifying decryption:\n" | |
| " m' = \n" | |
| "=c^d = " << c << '^' << d_ << '\n' | |
| << "=(m^e mod n)^d = (m^" << e_ << " mod " << n_ << ")^" << d_ << '\n' | |
| << "=m^(ed) mod n = m^(" << e_ << MUL << d_ << ") mod " << n_ << '\n' | |
| << "=m^(1+k" MUL PHI "(n)) \n" | |
| << "=m mod n = m mod " << n_ << "\n" | |
| << ((m == static_cast<intmax_t>(-1)) ? decrypt(c) : m) << '\n'; | |
| } | |
| intmax_t s(intmax_t m) const noexcept { | |
| assert(m >= 0); | |
| assert(d_ >= 0); | |
| assert(n_ >= 0); | |
| return iPowMod(m, d_, n_); | |
| } | |
| void verifySign(intmax_t m, intmax_t s) const noexcept { | |
| assert(n_ > 0); | |
| const auto &se = iPowMod(s, e_, n_); | |
| const auto &mn = m % n_; | |
| std::cout << "Verifying Signiture:\n" | |
| "s^e mod n = " << s << '^' << e_ << " mod " << n_ << " = " << se << '\n' | |
| << "m mod n = " << m << " mod " << n_ << " = " << mn << '\n'; | |
| if (se == mn) { | |
| std::cout << "So they are the same! Verified!\n"; | |
| } else { | |
| std::cout << "They are not the same! Check your signature!\n"; | |
| } | |
| } | |
| }; | |
| int main() { | |
| // Do not sync with C-style stdio | |
| #ifndef DEBUG_MODE | |
| std::ios::sync_with_stdio(false); | |
| std::cin.tie(nullptr); | |
| std::cout.tie(nullptr); | |
| #endif | |
| // n=pq | |
| // φ(n)=(p-1)(q-1) | |
| // pub key e | |
| // pvt key d | |
| // e * d == 1 mod φ(n) | |
| // message m | |
| // cipher text c=m^e_ mod n | |
| // decipher text m'=c^d mod n | |
| // Signing a message m: (m, s = m^d (mod n)) | |
| // Verifying a signature (m, s): check that s^e = m (mod n) | |
| const auto &rsa = [&]() { | |
| const auto choice = []() { | |
| char choiceX; | |
| std::cout << "First, you might want to construct an RSA instance!\n" | |
| "=====\n" | |
| "Supported options are: \n" | |
| "0) Run int power-mod calculator only (no RSA here)\n" | |
| "1) [n, RSA modulus] and [e, public key] (crack mode)\n" | |
| "2) [n, RSA modulus] and [d, private key] (normal mode)\n" | |
| "3) Run modulus-generator calculator only (no RSA here)\n" | |
| "=====\n" | |
| "Type a number to continue: "; | |
| std::cout.flush(); | |
| std::cin >> choiceX; | |
| return choiceX; | |
| }(); | |
| switch (choice) { | |
| case '0': { | |
| std::cout << "What is the base? "; | |
| std::cout.flush(); | |
| intmax_t base; | |
| std::cin >> base; | |
| std::cout << "What is the exponent? "; | |
| std::cout.flush(); | |
| intmax_t exp; | |
| std::cin >> exp; | |
| std::cout << "What is the modulus (-1 for no mod)? "; | |
| std::cout.flush(); | |
| intmax_t mod; | |
| std::cin >> mod; | |
| std::cout << '\n'; | |
| const auto &result = iPowMod(base, exp, mod, true); | |
| std::cout << "Power mod [" << base << '^' << exp << " mod " << mod << "] = [" << result | |
| << "].\n"; | |
| exit(0); | |
| } | |
| case '1': | |
| case '2': { | |
| const bool isE = choice == '1'; | |
| std::cout << "What is n (the RSA modulus)? "; | |
| std::cout.flush(); | |
| intmax_t n; | |
| std::cin >> n; | |
| std::cout << "What is " | |
| << (isE ? "e (the public" : "d (the private") << " key)? "; | |
| std::cout.flush(); | |
| intmax_t ed; | |
| std::cin >> ed; | |
| std::cout << '\n'; | |
| return isE ? Rsa::ne(n, ed) : Rsa::nd(n, ed); | |
| } | |
| case '3': { | |
| std::cout << "What is the modulus? "; | |
| std::cout.flush(); | |
| intmax_t mod; | |
| std::cin >> mod; | |
| std::cout << "What is the generator? "; | |
| std::cout.flush(); | |
| intmax_t g; | |
| std::cin >> g; | |
| std::cout << '\n'; | |
| const auto &result = modGenerator(mod, g); | |
| std::cout << "[g=" << g << "] is " << (result ? "" : "NOT ") | |
| << "a generator of modulus [Z_" << mod << "].\n"; | |
| exit(0); | |
| } | |
| default: { | |
| std::cerr << "ERR: Invalid option: [" << choice << "].\n"; | |
| exit(1); | |
| } | |
| } | |
| }(); | |
| for (;;) { | |
| std::cout << "\n=====\n" | |
| "What do you want to do?\n" | |
| "0) bye!\n" | |
| "1) encrypt a message\n" | |
| "2) decrypt a message\n" | |
| "3) sign a message\n" | |
| "4) verify a message\n" | |
| "=====\n" | |
| "Type a number to continue: "; | |
| std::cout.flush(); | |
| char choice; | |
| std::cin >> choice; | |
| switch (choice) { | |
| case '0': { | |
| exit(0); | |
| } | |
| case '1': { | |
| std::cout << "What is m (the message)? "; | |
| std::cout.flush(); | |
| intmax_t m; | |
| std::cin >> m; | |
| std::cout << '\n'; | |
| const auto &c = rsa.c(m); | |
| std::cout << "The cipher is: [c=" << c << "].\n\n"; | |
| break; | |
| } | |
| case '2': { | |
| std::cout << "What is c (the cipher)? "; | |
| std::cout.flush(); | |
| intmax_t c; | |
| std::cin >> c; | |
| std::cout << '\n'; | |
| const auto &m = rsa.decrypt(c); | |
| std::cout << "The original message is: [m=" << m << "].\n\n"; | |
| rsa.verifyDecrypt(c, m); | |
| std::cout << '\n'; | |
| break; | |
| } | |
| case '3': { | |
| std::cout << "What is m (the message)? "; | |
| std::cout.flush(); | |
| intmax_t m; | |
| std::cin >> m; | |
| std::cout << '\n'; | |
| const auto &s = rsa.s(m); | |
| std::cout << "The signature is: [m=" << m << ", s=" << s << "].\n\n"; | |
| rsa.verifySign(m, s); | |
| std::cout << '\n'; | |
| break; | |
| } | |
| case '4': { | |
| std::cout << "What is m (the message)? "; | |
| std::cout.flush(); | |
| intmax_t m; | |
| std::cin >> m; | |
| std::cout << "What is s (the signature)? "; | |
| std::cout.flush(); | |
| intmax_t s; | |
| std::cin >> s; | |
| std::cout << '\n'; | |
| rsa.verifySign(m, s); | |
| std::cout << '\n'; | |
| break; | |
| } | |
| default: { | |
| std::cerr << "ERR: Invalid option: [" << choice << "]. Retry!\n"; | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment