第1关：实验一：古典密码算法---代换技术
任务描述
本关任务：了解古典密码体制技术中的代换技术，并编程实现代换密码的加解密功能。
注意所有明文字符为26个小写字母，也就是说字母表为26个小写字母。
相关知识
为了完成本关任务，你需要掌握：1.古典密码算法，2.代换密码。
古典密码算法
古典密码算法历史上曾被广泛应用，大都使用手工和机械操作来实现加密和解密，比较简单。古典密码主要是利用密码算法实现文字信息的加密和解密，本实验运用两种常见的具有代表性的古典密码技术——代换密码技术，以帮助学员对密码算法建立一个初步的认识和印象。
代换密码
代换密码算法的原理是使用替代法进行加密，就是将明文中的字符用其它字符替代后形成密文。例如：明文字母a,b,c,d，用D,E,F,G做对应替换后形成密文。
代换密码包括多种类型，如单表替代密码，多明码替代密码，多字母替代密码，多表替代密码等。本实验利用一种典型的单表替代密码——恺撒caesar密码，又叫循环移位密码，加密方法是将明文中的每个字符，用此字符在字母表中后面第k个字母替代，加密过程可以表示为下面的函数：
E(m)=(m+k)(modn)
其中：m为明文字母在字母表中的位置数；n为字母表中的字母个数；k为密钥；E(m)为密文字母在字母表中对应的位置数。
例如，对于明文字母H，其在字母表中的位置数为8，设k=4，则按照上式计算出来的密文为L：
E(8)=(m+k)(modn)=(8+4)(mod26)=12=L
编程要求
本关的编程任务是补全右侧代码片段Encrypt和Dencrypt中Begin至End中间的代码，具体要求如下：
在Encrypt中，根据实验原理部分对凯撒密码算法的介绍，将明文字符串参数clearText通过密钥参数K加密转换成密文，并存入密文字符串参数变量cipherText。
在Dencrypt中，与Encrypt函数相对，将密文字符串参数cipherText通过密钥参数K解密转换成明文，并存入明文字符串参数变量clearText。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
4
internet
预期输出：
密钥：4
明文：internet
密文：mrxivrix
解密：internet输入格式：
第1行：整数k，表示密钥
第2行：待加密明文
输出格式：
第1行：输出密钥k
第2行：输出原始明文
第3行：输出加密后的密文
第4行：输出解密后的明文
开始你的任务吧，祝你成功！
//
// main.cpp
// step1
//
// Created by ljpc on 2018/10/16.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#define N 26
void Encrypt(int K, char* clearText, char* cipherText)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int len = strlen(clearText);
for (int i = 0; i < len; i++) {
if (clearText[i] >= 'a' && clearText[i] <= 'z') {
cipherText[i] = ((clearText[i] - 'a' + K) % N) + 'a';
}
else {
cipherText[i] = clearText[i];
}
}
cipherText[len] = '\0';
/********* End *********/
}
void Dencrypt(int K, char* clearText, char* cipherText)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int len = strlen(cipherText);
for (int i = 0; i < len; i++) {
if (cipherText[i] >= 'a' && cipherText[i] <= 'z') {
int temp = cipherText[i] - 'a' - K;
if (temp < 0) temp += N;
clearText[i] = temp + 'a';
} else {
clearText[i] = cipherText[i];
}
}
clearText[len] = '\0';
/********* End *********/
}
int main(int argc, const char * argv[]) {
int K;
char ClearText[100];
char ClearText2[100];
char CipherText[100];
scanf("%d", &K);
scanf("%s", ClearText);
printf("密钥：%d\n", K);
printf("明文：%s\n", ClearText);
Encrypt(K, ClearText, CipherText);
printf("密文：%s\n", CipherText);
Dencrypt(K, ClearText2, CipherText);
printf("解密：%s\n", ClearText2);
return 0;
}
第2关：实验二：古典密码算法---置换技术
任务描述
本关任务：了解古典密码体制技术中的置换技术，并编程实现置换密码的加解密功能。
相关知识
为了完成本关任务，你需要掌握：1.古典密码算法，2.置换密码。
古典密码算法
古典密码算法历史上曾被广泛应用，大都使用手工和机械操作来实现加密和解密，比较简单。古典密码主要是利用密码算法实现文字信息的加密和解密，本实验运用常见的具有代表性的古典密码技术——置换密码技术，以帮助学员对密码算法建立一个初步的认识和印象。
置换密码
置换密码又称为换位密码，算法的原理是不改变、替换明文字符，只将字符在明文中的排列顺序改变，从而实现明文信息的加密。
矩阵换位法是实现置换密码的一种常用方法（类似于教材中的双换位密码）。它将明文中的字母按照给定的顺序安排在一个矩阵中，然后用根据密钥提供的顺序重新组合矩阵中字母，从而形成密文。
例如,明文为attackbeginsatfive，密钥为1 4 5 3 2 6，将明文按照每行6列的形式排在矩阵中，形成如下形式：
根据密钥1 4 5 3 2 6给定一个置换：
根据上面的置换，将原有矩阵中的字母按照第1列，第4列，第5列，第3列，第2列，第6列的顺序排列，则有下面形式：
从而得到密文:abatgftetcnvaiikse。
其解密的过程是根据密钥的字母数作为列数，将密文按照列，行的顺序写出，再根据由密钥给出的矩阵置换产生新的矩阵，从而恢复明文。
注意，本实验为了迎合程序中下标使用惯例，所有索引从0开始，另外本实验重在实现置换的过程，所以本样例中的明文长度和密钥长度一直，无需重组为矩阵，详情参看样例。
编程要求
本关的编程任务是补全右侧代码片段Encrypt和Dencrypt中Begin至End中间的代码，具体要求如下：
在Encrypt中，根据实验原理部分对置换密码算法的介绍，将明文字符串参数clearText通过密钥表参数cipherTab加密转换成密文，并存入密文字符串参数变量cipherText。
在Dencrypt中，与Encrypt函数功能相反，将密文字符串参数cipherText通过密钥表参数cipherTab解密转换成明文，并存入明文字符串参数变量clearText。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
internet
4 7 3 1 2 6 0 5
预期输出：
密钥：
0 1 2 3 4 5 6 7
4 7 3 1 2 6 0 5
明文：internet
密文：rtentein
解密：internet输入格式：
第1行：待加密的明文
第2行：置换密钥，索引从0开始，密钥表大小等于与明文长度一直
输出格式：
第1~3行：密钥表信息
第4行：明文
第5行：密文
第6行：解密
开始你的任务吧，祝你成功！
第3关：实验三：DES加解密算法的实现
任务描述
本关任务：掌握DES加密算法的加解密过程，并且实现DES加解密算法中的各个功能模块。
相关知识
为了完成本关任务，你需要掌握：1.DES算法，2.DES加密，3.DES解密，4.子密钥的生成算法。
DES算法
DES(Data Encryption Standard)算法，于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。DES算法以被应用于许多需要安全加密的场合。
DES加密
DES算法把64位的明文输入块变为64位的密文输出块，它所使用的密钥也是64位，其功能是把输入的64位数据块按位重新组合，并把输出分为L0 、R0
两部分，每部分各长32位，其置换规则见下表：
58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,
即将输入的第58位换到第1位，第50位换到第2位，……，依此类推，最后一位是原来的第7位。L0
，R0则是换位输出后的两部分，L0是输出的左32位，R0是右32位，经过16次迭代运算后，得到L(16)和R(16)，将此作为输入，进行逆置换，即得到密文输出。
其中每一轮迭代的结构如下图所示：
迭代中的F函数如下图所示：
F函数中用到的8个BOX置换如下图所示：
DES解密
DES算法的解密过程是一样的，区别仅仅在于第一次迭代时用子密钥K16，第二次K15、……，最后一次用K1，算法本身并没有任何变化。
子密钥的生成算法
子密钥Ki(48bit)的生成算法初始Key值为64位，但DES算法规定，其中第8、16、......64位是奇偶校验位，不参与DES运算，故Key实际可用位数便只有56位。
将56位分为C0、D0两部分，各28位，然后分别进行第1次循环左移，得到C1、D1，将C1（28位）、D1（28位）合并得到56位，再经过缩小选择换位2，从而便得到了密钥K 1（48位），依此类推，便可得到K 1、K2、......、K16。
需要注意的是，16次循环左移对应的左移位数要依据下述规则进行：循环左移位数1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1。
其中置换选择1表如下：
置换选择2表如下：
编程要求
本关的编程任务是补全右侧代码片段ByteToBit、BitToByte、CYCLELEFT、SETKEY、Set_SubKey、S_BOXF、XOR、F_FUNCTION和DES中Begin至End中间的代码，具体要求如下：
- 在ByteToBit中，将字节组In转化成位组Outs，其中参数bits是每个字符占的位数，通常设置为8。
- 在BitToByte中，将位组In转换成字节组Outs，其中参数bits是每个字符占的位数，通常设置为8。
- 在CYCLELEFT中，循环左移位组In，所有位向左移动loop步，其中len是位组长度。
- 在SETKEY中，根据8个字节的字符串参数变量Key_C产生64位bool类型的密钥，每个字符占8位，左边高位，右边低位，并存入位组参数变量Key_B。
- 在Set_SubKey中，根据64位位组密钥生成16个48位的子密钥位组。
- 在S_BOXF中，根据S_BOX置换表，将48位位组In置换为32位位组Out。
- 在XOR中，将位组InA和InB按位异或，并将结果存入InA位组中，其中len是位组的长度。
- 在F_FUNCTION中，实现F函数里的扩展置换（EXPAND_32to48）、S盒置换（S_BOX）以及P盒置换（TRANS_32to32）。
- 在DES中，实现加解密算法，并通过Type参数来判断执行加密true还是解密false功能。
因为有些函数的实现存在多种方式，故生成的密钥会因程序具体实现而不同，主程序通过调用这些函数判断整个DES算法实现是否正确。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
romantic
2018helo
预期输出：
明文：romantic
明文：0x72 0x6f 0x6d 0x61 0x6e 0x74 0x69 0x63
明文：0111001001101111011011010110000101101110011101000110100101100011
密钥：2018helo
密钥：0x32 0x30 0x31 0x38 0x68 0x65 0x6c 0x6f
密钥：0011001000110000001100010011100001101000011001010110110001101111
解密：romantic
解密：0x72 0x6f 0x6d 0x61 0x6e 0x74 0x69 0x63
解密：0111001001101111011011010110000101101110011101000110100101100011
输入格式：
第1行：8字节长度的明文，8个字符
第2行：8字节长度的密钥，8个字符
输出格式：
如上样例输出
开始你的任务吧，祝你成功！
//
// des.cpp
// step3
//
// Created by ljpc on 2018/10/17.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include "des.h"
bool flag = true;
void print_bool(char* s, const bool *out, int len){
printf("%s: ", s);
for (int i=0; i<len; i++) {
printf("%d", out[i]);
}
printf("\n");
}
void SETKEY(const char Key_C[8], bool Key_B[64])
// Key_C: 2018helo
// ascii: 0x32 0x30 0x31 0x38 0x68 0x65 0x6c 0x6f
// 8bits: 00110010 00110000 00110001 00111000 01101000 01100101 01101100 01101111
// Key_B: 0011001000110000001100010011100001101000011001010110110001101111
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
for(int i=0; i<8; i++)
for(int j=0; j<8; ++j)
//Key_B[63-i*8-j] = ((Key_C[i]>>j) & 1);
Key_B[i*8+7-j] = ((Key_C[i]>>j) & 1);
/********* End *********/
}
void ByteToBit(bool *Outs, const char *In, int bits)
// In: password
// ascii: 0x70 0x61 0x73 0x73 0x77 0x6f 0x72 0x64
// 8bits: 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100
// Outs: 0111000001100001011100110111001101110111011011110111001001100100
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
for(int i=0; i<bits; i++)
for(int j=0; j<bits; ++j)
//Outs[63-i*bits-j] = ((In[i]>>j) & 1);
Outs[i*bits+bits-1-j] = ((In[i]>>j) & 1);
/********* End *********/
}
void BitToByte(char *Outs, const bool *In, int bits)
// In: 0111000001100001011100110111001101110111011011110111001001100100
// 8bits: 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100
// ascii: 0x70 0x61 0x73 0x73 0x77 0x6f 0x72 0x64
// Outs: password
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
for(int i=0; i<bits; i++){
int val = 0;
for (int j=0; j<bits; j++) {
//val = (val<<1) | In[63-i*bits-(bits-1-j)];
val = (val<<1) | In[i*bits+j];
}
Outs[i] = val;
}
Outs[bits] = '\0';
/********* End *********/
}
void CYCLELEFT(bool *In, int len, int loop) // 循环左移函数
// before: 0000000011110000111111110000
// loop: 1
// after: 0000000111100001111111100000
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
bool tmp[28];
memcpy(tmp, In, sizeof(tmp));
for (int i=0; i<len; i++) {
In[i] = tmp[(i+loop)%len];
}
/********* End *********/
}
void Set_SubKey(bool subKey[16][48], bool Key[64]) // 设置子密钥
// Key: 0011001000110000001100010011100001101000011001010110110001101111
// SubKey: 011000000011110001100100010111000101100101000100
// SubKey: 010000001011010001110100010111001000100011100100
// SubKey: 110001001100010001110110110000001110110011011001
// SubKey: 111001101100001100100010001010111011011000011001
// SubKey: 101010101001001100100011101110110101010100100010
// SubKey: 101010010001001001011011000011000100101100100110
// SubKey: 001001010101001011011000110101000110100011010100
// SubKey: 000101100101100111010000111000011000001011011001
// SubKey: 000101100100100101010001111000111010011010011000
// SubKey: 000011110110100100010101001110010001011100001111
// SubKey: 000011110010010110001101000111100101000010100110
// SubKey: 010110110000010010101001010001000110100111100101
// SubKey: 110110011000100010101000101000101010100011011001
// SubKey: 100100001010101010001110111000111001011100010011
// SubKey: 001100000011111000000110000111110000011100101010
// SubKey: 011100000011111000000100000101000101011101100110
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
bool realKey[56];
bool left[28];
bool right[28];
bool compressKey[48]; // 去掉奇偶标记位，将64位密钥变成56位
for (int i=0; i<56; i++){
realKey[i] = Key[TRANS_64to56[i]-1];
}
// 生成子密钥，保存在 subKeys[16] 中
for(int round=0; round<16; round++)
{
// 前28位与后28位
for(int i=0; i<28; i++)
left[i] = realKey[i];
for(int i=28; i<56; i++)
right[i-28] = realKey[i];
// 左移
CYCLELEFT(left, 28, SHIFT_TAB[round]);
CYCLELEFT(right, 28, SHIFT_TAB[round]);
for(int i=0; i<28; i++)
realKey[i] = left[i];
for(int i=28; i<56; i++)
realKey[i] = right[i-28];
// 压缩置换，由56位得到48位子密钥
for(int i=0; i<48; i++)
compressKey[i] = realKey[TRANS_56to48[i]-1];
for (int i=0; i<48; i++) {
subKey[round][i] = compressKey[i];
}
}
/********* End *********/
}
void XOR(bool *InA, const bool *InB, int len) // 异或函数
// Before InA: 000000000001011111111110100100000000001111111000
// Before InB: 011000000011110001100100010111000101100101000100
// Before InA: 011000000010101110011010110011000101101010111100
// Before InB: 011000000011110001100100010111000101100101000100
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
for (int i=0; i<len; i++) {
InA[i] = InA[i] ^ InB[i];
}
/********* End *********/
}
void S_BOXF(bool Out[32], const bool In[48])// S-盒代替函数
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int x = 0;
for(int i=0; i<48; i=i+6)
{
int row = In[i+0]*2 + In[i+5];
int col = In[i+1]*8 + In[i+2]*4 + In[i+3]*2 + In[i+4];
int num = S_BOX[i/6][row][col];
for (int k=3; k>=0; k--) {
Out[x+k] = num%2;
num /= 2;
}
x += 4;
}
/********* End *********/
}
void F_FUNCTION(bool In[32], const bool Ki[48]) // f 函数完成扩展置换、S-盒代替和P盒置换
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
// 第一步：扩展置换，32 -> 48
bool expandR[48];
for(int i=0; i<48; i++)
//expandR[47-i] = In[32-EXPAND_32to48[i]]; // 0x8c 0x22 0xe2 0x86 0x48 0x5a 0x4b 0xae
expandR[i] = In[EXPAND_32to48[i]-1]; // 0x8c 0x22 0xe2 0x86 0x48 0x5a 0x4b 0xae
// 第二步：异或
XOR(expandR, Ki, 48);
// 第三步：查找S_BOX置换表
bool output[32];
S_BOXF(output, expandR);
// 第四步：P-置换，32 -> 32
for(int i=0; i<32; i++){
In[i] = output[TRANS_32to32[i]-1];
}
/********* End *********/
}
void DES(char Out[8], char In[8], const bool subKey[16][48], bool Type) // 标准DES Type: True加密/False解密
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
bool plain[64];
bool left[32];
bool right[32];
bool newLeft[32];
bool cipher[64];
bool currentBits[64];
ByteToBit(plain, In, 8);
// 第一步：初始置换IP
for(int i=0; i<64; i++)
currentBits[i] = plain[TRANS_INIT[i]-1];
// 第二步：获取 Li 和 Ri
for(int i=0; i<32; i++)
left[i] = currentBits[i];
for(int i=32; i<64; i++)
right[i-32] = currentBits[i];
// 第三步：共16轮迭代
if (Type == true) { // 加密
for(int round=0; round<16; round++)
{
memcpy(newLeft, right, sizeof(newLeft));
F_FUNCTION(right,subKey[round]);
XOR(right, left, 32);
memcpy(left, newLeft, sizeof(left));
}
}
if (Type == false) { // 解密
for(int round=15; round>=0; round--)
{
memcpy(newLeft, right, sizeof(newLeft));
F_FUNCTION(right,subKey[round]);
XOR(right, left, 32);
memcpy(left, newLeft, sizeof(left));
}
}
// 第四步：合并L16和R16，注意合并为 R16L16
for(int i=0; i<32; i++)
//cipher[63-i] = left[31-i];
cipher[i] = right[i];
for(int i=32; i<64; i++)
//cipher[63-i] = right[31-(i-32)];
cipher[i] = left[(i-32)];
// 第五步：结尾置换IP-1
for(int i=0; i<64; i++)
currentBits[i] = cipher[i];
for(int i=0; i<64; i++)
cipher[i] = currentBits[TRANS_END[i]-1];
BitToByte(Out, cipher, 8);
/********* End *********/
}第4关：实验四：RSA加解密算法的实现
任务描述
本关任务：掌握RSA加密算法的加解密过程，并且实现RSA加解密算法中的各个功能模块。
相关知识
为了完成本关任务，你需要掌握：1.RSA加密算法，2.公钥和私钥的产生，3.加解密消息。
RSA加密算法
RSA加密算法是一种非对称加密算法。在公钥加密标准和电子商业中RSA被广泛使用。RSA是1977年由罗纳德•李维斯特（Ron Rivest）、阿迪•萨莫尔（Adi Shamir）和伦纳德•阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作，RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA算法的可靠性基于分解极大的整数是很困难的。假如有人找到一种很快的分解因子的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。
公钥和私钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个密钥：
step1：随意选择两个大的质数p和q，p不等于q，计算N=pq。
step2：根据欧拉函数，不大于N且与N互质的整数个数为(p−1)(q−1)。
step3：选择一个整数e与(p−1)(q−1)互质，并且e小于(p−1)(q−1)。
step4：用以下这个公式计算d：d×e≡1(mod(p−1)(q−1))。
step5：将p和q的记录销毁。
其中e是公钥，d是私钥。d是秘密的，而N是公众都知道的，Alice将她的公钥传给Bob，而将她的私钥藏起来。
加解密消息
假设Bob想给Alice送一个消息m，他知道Alice产生的N和e，用下面这个公式他可以将m加密为c：
c=m
e
(modn)
计算c并不复杂，Bob算出c后就可以将它传递给Alice。
Alice得到Bob的消息c后就可以利用她的密钥d来解码，她可以用以下这个公式来将c转换为m：
m=c
d
((modn))
最终她可以将原来的信息m重新复原。
编程要求
本关的编程任务是补全右侧代码片段PRIME、mod、exgcd、Inv、GCD和ModPow中Begin至End中间的代码，具体要求如下：
在PRIME中，借助全局数组变量p用素数筛法求10000以内的所有素数，并存入全局数组变量prime中。
在mod中，计算64位整型参数变量a在参数变量n下的模。
在exgcd中，根据参数a、b、c实现扩展欧几里得ax+by=c，并将结果存入x、y。
在Inv中，借助exgcd函数计算参数a在模n下的逆元。
在GCD中，求两个整数a和b的最大公约数。
在ModPow中，计算a的b次幂在模n下的结果x≡a
b
(modn)。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
14 16
465
预期输出：
素数：47 59
公开N：2773
欧拉T：2668
公钥E：3
私钥D：1779
明文：465
密文：1191
解密：465输入格式：
第1行：整数p1和p2，表示素数表中的第一个素数
第2行：整型数据，明文
输出格式：
如上样例8行输出
开始你的任务吧，祝你成功！
//
// main.cpp
// step4
//
// Created by ljpc on 2018/10/16.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define int64 long long
int prime[2001]; //存放素数
int p[10001]; //用筛选法求素数
void PRIME()
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int i,i2,k;
for(i=0;i<=10000;i+=2)
p[i]=0;
for(i=1;i<=10000;i+=2)
p[i]=1;
p[2]=1;p[1]=0;
for(i=3;i<=100;i+=2)
{
if(p[i]==1)
{
i2=i+i;
k=i2+i;
while(k<=10000)
{
p[k]=0;
k+=i2;
}
}
}
int t = 0;
prime[t++]=2;
for(i=3;i<=10000;i+=2)
if(p[i])
prime[t++]=i;
/********* End *********/
}
int64 mod(int64 a,int64 n)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
return (a%n+n)%n;
/********* End *********/
}
void exgcd(int64 a,int64 b,int64 &d,int64 &x,int64 &y)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
if(b==0)
{
d=a;
x=1;
y=0;
return;
}
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
/********* End *********/
}
//a-1 mod n
int64 Inv(int64 a,int64 n) // 计算逆元素
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int64 d,x,y;
exgcd(a,n,d,x,y);
if(d==1)
return mod(x,n);
else
return -1;
/********* End *********/
}
//求两个数的最大公约数
int64 GCD(int64 n,int64 m)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int64 t,r;
if(n<m)
{
t=n;
n=m;
m=t;
}
while((r=n%m)!=0)
{
n=m;
m=r;
}
return m;
/********* End *********/
}
//x=a^b(mod n)
int64 ModPow(int64 a,int64 b,int64 n)
{
// 请在这里补充代码，完成本关任务
/********* Begin *********/
int64 d=1,i=0;
while(b>=(1<<i)) i++;
for(--i;i>=0;--i)
{
d=d*d%n;
if(b&(1<<i))
d=d*a%n;
}
return d;
/********* End *********/
}
int main(int argc, const char * argv[]) {
PRIME();
int64 P1, P2;
int64 T;
int64 N;
int64 E;
int64 D;
int64 M;
int64 C;
int64 m;
scanf("%lld %lld", &P1, &P2);
scanf("%lld", &M);
P1 = prime[P1];
P2 = prime[P2];
T = (P1-1)*(P2-1);
N = P1 * P2;
for(int64 i=2; i<T; i++)
if(GCD(T, i)==1){
E = i;
break;
}
D = Inv(E, T);
C = ModPow(M,E,N);
m = ModPow(C,D,N);
printf("素数：%lld %lld\n", P1, P2);
printf("公开N：%lld\n",N);
printf("欧拉T：%lld\n",T);
printf("公钥E：%lld\n",E);
printf("私钥D：%lld\n",D);
printf("明文：%lld\n",M);
printf("密文：%lld\n",C);
printf("解密：%lld\n",m);
return 0;
}
