rsa.cpp

一个加密程序 一个加密程序 一个加密程序 一个加密程序

/*
  Author:  qiyufeng

  Exercise
  "4.6 Two samples of RSA cipertext are presented in
  Tables 4.1 and 4.2. Your task is to decrypt them.
  The public parameters of the system are n = 18923
  and b = 1261 (for Table 4.1) and n = 31313 and
  b = 4913 (for Table 4.2)." 
  See "Cryptography: Theory and Practice"  pages 157-158.
*/

#include <math.h>
#include <stdio.h>

#define BITS_PER_LONG   32l
#define BITS_PER_LONG_1 31l

long get_bit(long i, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;

  return (sieve[c] >> (BITS_PER_LONG_1 - b)) & 1;
}

void set_bit(long i, long v, long *sieve)
{
  long b = i % BITS_PER_LONG;
  long c = i / BITS_PER_LONG;
  long mask = 1 << (BITS_PER_LONG_1 - b);

  if (v == 1)
    sieve[c] |= mask;
  else
    sieve[c] &= ~mask;
}

void Sieve(long n, long *sieve)
{
  long c, i, inc;

  set_bit(0l, 0l, sieve);
  set_bit(1l, 0l, sieve);
  set_bit(2l, 1l, sieve);
  for (i = 3; i <= n; i++)
    set_bit(i, i & 1, sieve);
  c = 3;
  do {
    i = c * c, inc = c + c;
    while (i <= n) {
      set_bit(i, 0l, sieve);
      i += inc;
    }
    c += 2;
    while (!get_bit(c, sieve)) c++;
  } while (c * c <= n);
}

long factor(long n, long *sieve)
/* factor using trial division */
{
  int found = 0;
  long p = 0, s = (long)sqrt(n);

  while (!found && p <= s) {
    while (!get_bit(p, sieve)) p++;
    found = n % p == 0;
    if (!found) p++;
  }
  return p;
}

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

long exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1l, s = x;

  while (b != 0) {
    if (b & 1l) a = (a * s) % n;
    b >>= 1;
    if (b != 0) s = (s * s) % n;
  }
  return a;
}

int main(void)
{
  char abc[27] = "abcdefghijklmnopqrstuvwxyz";
  long b[2] = {1261l, 4913l};
  long n[2] = {18923l, 31313l};
  long c[2][32] = {{12423l, 11524l,  7243l,  7459l,
                    14303l,  6127l, 10964l, 16399l,
                     9792l, 13629l, 14407l, 18817l,
                    18830l, 13556l,  3159l, 16647l,
                     5300l, 13951l,    81l,  8986l,
                     8007l, 13167l, 10022l, 17213l,
                     2264l,   961l, 17459l,  4101l,
                     2999l, 14569l, 17183l, 15827l},
                   { 6340l,  8309l, 14010l,  8936l,
                    27358l, 25023l, 16481l, 25809l,
                    23614l,  7135l, 24996l, 30590l,
                    27570l, 26486l, 30388l,  9395l,
                    27584l, 14999l,  4517l, 12146l,
                    29421l, 26439l,  1606l, 17881l,
                    25774l,  7647l, 23901l,  7372l,
                    25774l, 18436l, 12056l, 13547l}};
  long i, j, sieve[10000], m, p, q;
  long a, bi, ni, phi, t;

  Sieve(n[1], sieve);
  for (i = 0; i < 2; i++) {
    bi = b[i];
    ni = n[i];
    p = factor(ni, sieve);
    q = ni / p;
    printf("p = %5ld q = %5ld n = %5ld\n", p, q, ni);
    phi = (p - 1) * (q - 1);
    a = Extended_Euclidean(bi, phi);
    printf("a = %5ld b = %5ld\n", a, bi);
    printf("%5ld * %5ld mod %5ld = %5ld\n", a, bi,
           phi, (a * bi) % phi);
    for (j = 0; j < 32; j++) {
      m = exp_mod(c[i][j], a, ni);
      if (c[i][j] != exp_mod(m, bi, ni))
        printf("*error*\n RSA\n");
      t = m / 676l;
      m = m % 676l;
      printf("%c", abc[t]);
      t = m / 26l;
      m = m % 26l;
      printf("%c", abc[t]);
      printf("%c", abc[m]);
      if ((j + 1) % 8 == 0) printf("\n");
    }
    printf("\n");
  }
  return 0;
}