шифрование: алгоритм RSA

Question

Я реализую алгоритм RSA для шифрования и дешифрования, как указано здесь:

http://www.di -mgt.com.au / rsa_alg.html

Но могне понимаю часть генерации случайных простых чисел в генерации ключей.Поэтому я беру два простых числа в качестве входных данных от пользователя.У меня были трудности с генерацией е тоже.поэтому я сделал его постоянным (e = 17)

Некоторые простые числа работают правильно (т.е. правильно кодируют и декодируют) в gcc под linux, но не в devcpp под windows.(например, 53,61)

Вот код генерации ключа:

/* Generates private and public keys and saves into two separate files */
void keygen()
{
    int p,q,phi,d,e,n,s;

    printf("\n Enter two prime numbers: ");
    scanf("%d%d",&p,&q);

    n = p*q;
    phi=(p-1)*(q-1);

    e=17;

    // selec d such that d*e = 1+ k*phi for some integer k.
    d = 0;
    do
    {
        d++;
        s = (d*e)%phi;
    }while(s!=1);

    printf("\n public key: { e=%d n=%d }",e,n);
    printf("\n private key: { d=%d n=%d }\n",d,n);

}

Нужна помощь и предложения по простому числу и генерации е.

Answer 1

так что вы уже знаете, что e * d должно соответствовать 1 mod phi (n)

, поскольку вы знаете, что phi (n) кортеж (e, d) может быть рассчитан с использованием расширенного евклидоваАлгоритм (EEA):

выберите целое число для e (обычно небольшое целое число; это будет публичный показатель, шифрование будет быстрее с меньшими показателями), которое меньше phi (n) и больше 2 (? ... я думаю)

когда у вас есть кандидат на e, вычислите наибольший общий делитель (gcd) для e, а phi (n) ... должно быть 1 ... если нет, выберитеновый кандидат для e и repeat (поскольку не было бы никакого модульного обратного, другими словами, для этого e и phi (n) не существует частного показателя d *

после того, как вы знаете, что gcd (e, phi (n)) == 1 вы можете рассчитать d, используя EEA (или в качестве ярлыка, рассчитать EEA напрямую, поскольку он также предоставит GCD ... если это не 1, выберите новое значение для e)

EEA (быстро и грязно для вычисления модульного обратного):

представьте таблицу с 3 столбцами:

Допустим, эти столбцы имеют имена: b, q и t

, поэтому строки этой таблицы будут выглядеть следующим образом:

b0, q0, t0
b1, q1, t1
...
(и т. Д.)

первые 2 строки будут изначально заполнены.для всех остальных строк есть правило итерации, которое можно применить к двум предыдущим строкам, что приведет к значениям для следующей строки

первые 2 строки:

phi (n), NO_VALUE, 0
e, floor (phi (n) / e), 1

итеративное правило для создания следующей строки: (где [] - оператор индекса для выбора строки)

b [i] = b [i-2] mod b [i-1]
q [i] = b [i-1] / b [i] (целочисленное деление, без дробей ...)
t [i] = t [i-2] - (q [i-1] * t [i-1])

вы можете прервать схему, когда b [i] становится равным 0или 1 ... вам не нужно q для последней строки ...

, поэтому, если b [i] равно 0, b [i-1] не может быть 1, так как вы должны были прерваться, когдаВы вычислили b [i-1], если это было 1 ...

, если вы достигли b [i] == 0, b [i-1] - это ваш gcd ..., так как это не 1 вынужно новое значение для e

, если b [i] == 1 ваш gcd равен 1, и есть обратное значение ... и это t [i] (если t отрицательно, добавьте phi (n))

пример с реальными значениями:

давайтескажем, phi (n) равно 120, скажем, мы выбираем 23 в качестве кандидата на e

наша таблица будет выглядеть так:

b     q     t
120   –     0
23    5     1
5     4     -5
3     1     21
2     1     -26
1     2     47

последний вычисленный b равен 1, так что => gcd (23 120) == 1 (доказательство: обратное существует)
последнее вычисленное t равно 47 => 23 * 47 mod 120 == 1 (t является обратным)

Answer 2

Dear Friend just follow this algorithm

 Key generation
1) Pick two large prime numbers p and q, p != q;
2) Calculate n = p × q;
3) Calculate ø (n) = (p − 1)(q − 1);
4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e <  ø (n);
5) Calculate d, so that d · e mod ø (n) = 1, i.e., d is the multiplicative inverse of e in mod  ø (n);
6) Get public key as KU = {e, n};
7) Get private key as KR = {d, n}.
Encryption
For plaintext block P < n, its ciphertext C = P^e (mod n).
Decryption
For ciphertext block C, its plaintext is P = C^d (mod n).

Code:
#include<stdio.h> 
#include<conio.h> 
#include<stdlib.h> 
#include<math.h> 
#include<string.h> 

long int p,q,n,t,flag,e[100],d[100],temp[100],j,m[100],en[100],i; 
char msg[100]; 
int prime(long int); 
void ce(); 
long int cd(long int); 
void encrypt(); 
void decrypt(); 
void main() 
{ 
clrscr(); 
printf("\nENTER FIRST PRIME NUMBER\n"); 
scanf("%d",&p); 
flag=prime(p); 
if(flag==0) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER ANOTHER PRIME NUMBER\n"); 
scanf("%d",&q); 
flag=prime(q); 
if(flag==0||p==q) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER MESSAGE\n"); 
fflush(stdin); 
scanf("%s",msg); 
for(i=0;msg[i]!=NULL;i++) 
m[i]=msg[i]; 
n=p*q; 
t=(p-1)*(q-1); 
ce(); 
printf("\nPOSSIBLE VALUES OF e AND d ARE\n"); 
for(i=0;i<j-1;i++) 
printf("\n%ld\t%ld",e[i],d[i]); 
encrypt(); 
decrypt(); 
getch(); 
} 
int prime(long int pr) 
{ 
int i; 
j=sqrt(pr); 
for(i=2;i<=j;i++) 
{ 
    if(pr%i==0) 
    return 0; 
} 
return 1; 
} 
void ce() 
{ 
int k; 
k=0; 
for(i=2;i<t;i++) 
{ 
    if(t%i==0) 
    continue; 
    flag=prime(i); 
    if(flag==1&&i!=p&&i!=q) 
    { 
        e[k]=i; 
        flag=cd(e[k]); 
        if(flag>0) 
        { 
            d[k]=flag; 
            k++; 
        } 
        if(k==99) 
        break; 
    } 
} 
} 
long int cd(long int x) 
{ 
long int k=1; 
while(1) 
{ 
    k=k+t; 
    if(k%x==0) 
    return(k/x); 
} 
} 
void encrypt() 
{ 
long int pt,ct,key=e[0],k,len; 
i=0; 
len=strlen(msg); 
while(i!=len) 
{ 
    pt=m[i]; 
    pt=pt-96; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
        k=k*pt; 
        k=k%n; 
    } 
    temp[i]=k; 
    ct=k+96; 
    en[i]=ct; 
    i++; 
} 
en[i]=-1; 
printf("\nTHE ENCRYPTED MESSAGE IS\n"); 
for(i=0;en[i]!=-1;i++) 
printf("%c",en[i]); 
} 
void decrypt() 
{ 
long int pt,ct,key=d[0],k; 
i=0; 
while(en[i]!=-1) 
{ 
    ct=temp[i]; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
        k=k*ct; 
        k=k%n; 
    } 
    pt=k+96; 
    m[i]=pt; 
    i++; 
} 
m[i]=-1; 
printf("\nTHE DECRYPTED MESSAGE IS\n"); 
for(i=0;m[i]!=-1;i++) 
printf("%c",m[i]); 
}

Answer 3

Следуя практическим примечаниям в конце связанной страницы, вы получите что-то вроде этого для простого поколения:

unsigned int get_prime(int e)
{
    while (true)
    {
        unsigned int suspect = 1 + (unsigned int)(65535.0 * rand() / (RAND_MAX + 1.0));
        suspect &= 0x0000FFFF; // make sure only the lower 16bit are set
        suspect |= 0xC001; // set the two highest and the lowest bit
        while (!test_prime(suspect))
        {
            suspect += 2;
        }
        if (suspect < 65536 && gcd(e, suspect - 1) == 1)
            return suspect;
    }
}

test_prime предполагается как реализация теста Миллера-Рабина . Функция выше делает определенные предположения и имеет некоторые недостатки:

• int это 32 бита
• RAND_MAX больше 65536
• rand() обычно не является хорошим генератором случайных чисел для серьезного шифрования
• Сгенерированные простые числа 16-битные, так что, очевидно, недостаточно для серьезного шифрования в любом случае

Не используйте это в любом производственном коде.

Согласно статье кажется правильным выбрать e фиксированный.

Answer 4

У меня нет ответа, но если один и тот же код, скомпилированный с двумя разными компиляторами, дает разные ответы, я бы предположил, что некоторые типы имеют разный размер или вы неявно полагаетесь на неопределенное поведение где-то.

Первое, что вы должны сделать, при наличии одинаковых пар простых чисел, убедиться, что все сгенерированные вами константы одинаковы в обеих реализациях.Если нет, то ваши алгоритмы генерации пары ключей ошибочны.

Следующее, что нужно сделать, - убедиться, что ваши входные данные для шифрования абсолютно идентичны в обеих системах.Обратите особое внимание на то, как вы справляетесь с символами конца строки.Имейте в виду, что в Windows конец строки равен \r\n, а в Linux - \n.Большинство реализаций библиотеки Windows преобразуют \r\n в \n при считывании файла, если "r" указано в качестве параметра режима для fopen().Ваша реализация может отличаться.

Наконец, какова бы ни была проблема, ни в коем случае никогда не используйте gets() Если вы даже поймаете себя на мысли, что будете использовать его снова, вы должны удалить лобные доливашего мозга с помощью ледоруба.