《信息系统安全》课程实验指导

第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 26void 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 -> 48bool expandR[48];for(int i=0; i<48; i++)//expandR[47-i] = In[32-EXPAND_32to48[i]]; // 0x8c 0x22 0xe2 0x86 0x48 0x5a 0x4b 0xaeexpandR[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 -> 32for(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);// 第一步：初始置换IPfor(int i=0; i<64; i++)currentBits[i] = plain[TRANS_INIT[i]-1];// 第二步：获取 Li 和 Rifor(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，注意合并为 R16L16for(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-1for(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);elsereturn -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;
}