Упражнение 10. Цифров подпис

Задача 1. Да се намери остатъкът на числото 3^256 разделено на 4 ( 3^256%4=?):

Задача 2. Да се намери остатъкът на числото 85^256 разделено на 83 ( 85^256%83=?):

Задача 3. Да се тества програмата. Допълнете програмата, така че да генерира и избира автоматично стойност за експонентата на публичния ключ

/*********************************************************************\
 * Title: RSA
 * Description: Генериране на ключове, криптиране и декриптиране с RSA 
 * Edited by: ilianko
 * Idea:  http://cppgm.blogspot.com/2008/01/rsa-algorithm.html
 * 
\*********************************************************************/

#include <stdio.h>

int r; // pRivate key exponent
int u; // pUblic key exponent
int phi; // phi(s) = (v-1)*(t-1) - Euler's totient function
int M; // Message
int C; // encrypted message
int s; // modulus for both the public and private keys, модул (делител) на ключовете


int check()
{
  int i, iMax;
  iMax = ( u > phi) ? u : phi;
  for( i=3; i < iMax ; i = i+2)
  {
    if(u%i==0 && phi%i==0) return 1;
  }
  return 0;
};

void encrypt()
{
  int i;
  
  C = 1;
  for(i=0; i < u; i++)
    C = C*M%s; //  modular arithmetic
  
  C = C%s;
  printf( "\n\tEncrypted keyword : %d", C );
}

void decrypt()
{
  int i;
  M = 1;
  for(i=0; i < r;i++)
    M=M*C%s;
  M = M%s;
  printf("\n\tDecrypted keyword : %d",M);
}

int main()
{
  int v,t; /* Изходящи праметри, избират се две произволни прости числа,
            * колкото по-големи, толкова "по-изчислителноемко" е разбиването. */
  int temp = 0;
  printf("Enter Two Prime Numbers\t: ");
  scanf("%d%d",&v,&t);
  
  s = v*t; // модул на ключовете
  phi=(v-1)*(t-1); // Euler's totient function
  
  printf("\n\t Phi(s)\t= %i", phi);
  
  do
  {
    printf("\n\n Enter public key exponent\t: ");
    scanf("%d",&u);
  }while( check() ); //Проверка дали избраната експонента е относително проста

  
  r = 1;
  while(temp != 1 )
  {
    temp = (r*u)%phi;
    r++;
  };
  r--;
  
  printf("\n\tPublic Key\t: {%d,%d}",u,s);
  printf("\n\tPrivate Key\t: {%d,%d}",r,s);
  
  printf("\n\nEnter The Plain Text\t: ");
  scanf("%d",&M);
  encrypt();
  
  printf("\n\nEnter the Cipher text\t: ");
  scanf("%d",&C);
  decrypt();
  
  return 0;
}