c - rsa 算法：任何人都可以向我解释发生了什么

Question

#include <string.h>
#include <conio.h>
#include <math.h>

int mult(unsigned int x, unsigned int y, unsigned int n) {
    unsigned long int k = 1;
    int j;
    for (j = 1; j <= y; j++)
        k = (k * x) % n;
    return (unsigned int) k;
}

void main() {
    char msg[100];
    unsigned int pt[100], ct[100], n, d, e, p, q, i;
    printf("Enter message : ");
    gets(msg);
    //strcpy(pt, msg);
    for (i = 0; i < strlen(msg); i++)
        pt[i] = msg[i];
    n = 253;
    d = 17;
    e = 13;
    printf("\nCT = ");
    for (i = 0; i < strlen(msg); i++)
        ct[i] = mult(pt[i], e, n);
    for (i = 0; i < strlen(msg); i++)
        printf("%d ", ct[i]);
    printf("\nPT = ");
    for (i = 0; i < strlen(msg); i++)
        printf("%c", pt[i]);
    for (i = 0; i < strlen(msg); i++)
        pt[i] = mult(ct[i], d, n);
}

这是实现 RSA 算法的简单程序，任何人都可以向我解释这里发生了什么以及为什么特别是 n=253、d=17、e=13。

帮助将不胜感激。

Answer 1

http://en.wikipedia.org/wiki/RSA_ (算法)。

253=11*23, // n=253 是两个“大”素数 p,q 的乘积

φ(n)=10*22=220。// Euler totient 函数是从 p,q
e= 13 // 一个小数，即与 phi(n) 互质的。然后计算 d，即 e*d=1 mod 220 --> d=17
-> d*e=221 === 1 mod 220。

扔掉 p,q。