Thanks for the question.
Here is how RSA encryption/decryption works
if c = m^e mod n
then m = c^d mod n
The first line above represents the encryption of a message m with a public key e to produce ciphertext c.
The second line above represents the decryption of a ciphertext c with a private key d to produce message m.
Both the public key e and private key d depend on the public modulus n.
where
m is some message
c is the ciphertext of m
e is a public key, a large integer relatively prime to s
d is a private key, a large integer relatively prime to s
n is a public modulus, the product of p and q
p is a large prime
q is a large prime
s is a secondary (private) modulus equal to the product of (p-1) and (q-1)
we choose s this way so that there is
an easy solution to the euler phi function.
recall if n = p*q and p and q are prime, then
phi(n) = phi(pq) = phi(p)*phi(q) = (p-1)*(q-1) = s
we choose e relatively prime to s.
then we know it has an inverse d
and we can use the euclidian algorithm to find it.***
So if Bob wants to get an encrypted message from anyone,
he generates p, q, s, e, d. He publishes e and n,
and keeps d, p, q, s private.
Now if Alice wants to send an encrypted message to Bob,
she simply grabs n and e from some public key server,
then calculates
c = m^e mod n
And sends c to Bob.
When Bob gets the encrypted message c he calculates
m = c^d mod n
and if he can 'recognize it' he accepts it
as a message encrypted only for him.
that is, he is the only one in the world
who can read the encrypted message.
this works because
c^d = (m^e)^d = m^(ed) = m^1 = m
This is not to say that Bob knows the ciphertext c came from Alice. We can cover digital signatures in another post if you like. However, I suspect you can figure out how to do it with the RSA. Pam! Inverse alert! Map!
The security of the RSA relies on the empirical
observation that no one to date has a found a good
way to factor n = p * q when given just n and e
where p and q are very large primes.
that's not to say that nsa or someone
else doesn't know how to do it or won't figure
it out in the future. it's considered extremely unlikely
by crypto geeks, however.
Bill
ps
below is a link to an RSA homework assignment
http://www2.ics.hawaii.edu/~wes/ICS623/Assignments/RSA.html
and some code that goes with it.
*** "How do you calculate d if you know n and s?
d is the inverse of e mod s.
There are two ways.
One way to do that is to use the euclidean algorithm.
You have to choose e relatively prime to s, i. e. GCD(e,s)=1.
Then using the Eudlidean division algorithm,
you can find c and d such that 1 = c*s + d*e.
Then 1 = d*e mod s, and d is the required number.
The other way is to find t = phi(s).
Then since e^t=1 mod s, then d = e^(t-1) is the inverse of e.
To do that you have to be able to factor s,
which in general is very difficult to do." --wes
(See 'unit 10' below for an example of where it's not difficult to factor s.)
/*
* Bill Luoma
* Ics 623
* unit 10 RSA
*
given p, q, a, and b prime
where p = 2a + 1 and q = 2b + 1,
let n = pq
let s = phi(n) = phi(pq) = phi(p)phi(q) = (p-1)(q-1)
= (2a+1-1)(2b+1-1) = 4ab =(2^2)(a)(b) which
is a unique factorization of primes.
Now phi(s) = phi(2^2ab) = phi(2^2)phi(a)phi(b) = 2(a-1)(b-1)
let t = phi(s) and let e and t be integers > 0
and let e be relatively prime to t
then e^t = 1 mod s
and since e^(t-1) * e = e^t = 1 mod s
e^(t-1) = e^(-1) mod s
To decrypt RSA, one needs to solve
m = c^d mod n
where d = e^(-1) mod s
So to decrypt the ciphertext c,
we should set m = c^(e^(t-1) mod s) mod n,
where t = 2(a-1)(b-1) mod s
and s = (p-1)(q-1) mod n
and e, the encryption key, are given.
*/
#include
#include
#include
#include
typedef unsigned long UL;
/* compare a k-word number, little endian */
/* return -1 if a(b, 0 if a=b, and 1 if a)b */
int mcmp(UL *a, UL *b, int k);
void madd(UL *a, UL *b, UL *P);
void msub(UL *a, UL *b, UL *P);
void mshl(UL *a, UL *P);
void mmpy(UL *a, UL *b, UL *c, UL *P);
void mexp(UL *a, UL *b, UL *c, UL *P);
void ddiv(UL *dd, UL *dv);
/* util */
UL rr(UL *b, UL k);
void sput(char *b, UL *a);
void sget(UL *a, char *b);
int read_num_1024(char* filename, UL num_1024[32]);
void gen_random_1021(UL r[32]);
double get_time_diff(struct timeval start, struct timeval finish);
/* Wes Peterson's assembly routines */
/* works with cygwin */
/* ar -rcsv asmath.lib add.obj sub.obj shl.obj */
/* gcc -ou9 luoma_p9.c -L./ -lasmath */
int add(UL *a, UL *b, int c);
int sub(UL *a, UL *b, int c);
int shl(UL *a, int c);
char buf[2048];
char bytes[512];
char nums[512];
UL one[32];
UL two[32];
UL result[32];
UL p[32], q[32], s[32], t[32], n[32];
UL a[32], b[32], c[32], d[32], e[32], m[32];
int main(int argc, char** argv)
{
int i = 0, flag = 0, size = 0;
UL start, stop;
FILE* file;
char* buf_ptr = NULL;
int bytes_read = 0;
struct timeval beg, end;
start = time(0);
printf("start time: %d\n", start);
one[0] = 1;
two[0] = 2;
file = fopen("input.txt", "r");
if (file) {
fread(buf, 1, sizeof(buf), file);
}
else {
printf("couldn't open input.txt\n");
exit(1);
}
//printf("read input: \n%s\n", buf);
buf_ptr = strstr(buf, "n=");
if (buf_ptr != NULL) {
sget(n, buf_ptr+3);
printf("n\n");
sput(nums, n);
printf(nums);
}
buf_ptr = strstr(buf, "p=");
if (buf_ptr != NULL) {
sget(p, buf_ptr+3);
printf("p\n");
sput(nums, p);
printf(nums);
}
buf_ptr = strstr(buf, "q=");
if (buf_ptr != NULL) {
sget(q, buf_ptr+3);
printf("q\n");
sput(nums, q);
printf(nums);
}
buf_ptr = strstr(buf, "a=");
if (buf_ptr != NULL) {
sget(a, buf_ptr+3);
printf("a\n");
sput(nums, a);
printf(nums);
}
buf_ptr = strstr(buf, "b=");
if (buf_ptr != NULL) {
sget(b, buf_ptr+3);
printf("b\n");
sput(nums, b);
printf(nums);
}
buf_ptr = strstr(buf, "c=");
if (buf_ptr != NULL) {
sget(c, buf_ptr+3);
printf("c\n");
sput(nums, c);
printf(nums);
}
buf_ptr = strstr(buf, "e=");
if (buf_ptr != NULL) {
sget(e, buf_ptr+3);
printf("e\n");
sput(nums, e);
printf(nums);
}
gettimeofday(&beg, NULL);
//let s = phi(n) = phi(pq) = phi(p)phi(q) = (p-1)(q-1) mod n
msub(p, one, n);
printf("p-1\n");
sput(nums, p);
printf(nums);
msub(q, one, n);
printf("q-1\n");
sput(nums, q);
printf(nums);
mmpy(p, q, s, n);
printf("s = phi(pq)\n");
sput(nums, s);
printf(nums);
//let t = phi(s) = phi(2^2ab) = phi(2^2)phi(a)phi(b) = 2(a-1)(b-1) mod s
msub(a, one, s);
printf("a-1\n");
sput(nums, a);
printf(nums);
msub(b, one, s);
printf("b-1\n");
sput(nums, b);
printf(nums);
mmpy(a, b, result, s);
printf("(a-1)(b-1)\n");
sput(nums, result);
printf(nums);
mmpy(result, two, t, s);
printf("t = phi(s)\n");
sput(nums, t);
printf(nums);
//d = e^(-1) = e^(t-1) mod s
msub(t, one, s);
printf("t-1\n");
sput(nums, t);
printf(nums);
mexp(e, t, d, s);
printf("e^(t-1)\n");
sput(nums, d);
printf(nums);
//m = c^d mod n
mexp(c, d, m, n);
printf("m:\n");
sput(nums, m);
printf(nums);
memset(buf, 0, sizeof(buf));
buf_ptr = (char*)m;
for (i = 127; i >= 0; i--) {
buf[127 - i] = buf_ptr[i];
}
printf("as string:\n%s\n", buf);
gettimeofday(&end, NULL);
printf("%d: decrypt took: %g s\n", i, get_time_diff(beg, end));
return 0;
}
int read_num_1024(char* filename, UL num_1024[32])
{
int bytes_read = 0;
char bytes[512]={0};
FILE* file = fopen(filename, "r");
if (!file) {
printf("couldn't open file p.txt\n");
exit(1);
}
bytes_read = fread(bytes, 1, sizeof(bytes), file);
fclose(file);
sget(num_1024, bytes);
return bytes_read;
}
int mcmp(UL *a, UL *b, int k)
{
int i;
for(i = k-1; i>=0; i--) {
if(a[i]>b[i]) return 1;
else if(a[i](b[i]) return -1;
}
return 0;
}
void madd(UL *a, UL *b, UL *P)
{
add(a+16, b+16, add(a, b, 0));
if(mcmp(a, P, 32)>=0) sub(a+16, P+16, sub(a, P, 0));
}
void msub(UL *a, UL *b, UL *P)
{
if(sub(a+16, b+16, sub(a, b, 0)))
add(a+16, P+16, add(a, P, 0));
}
void mshl(UL *a, UL* P)
{
shl(a+16, shl(a, 0));
if(mcmp(a, P, 32)>=0) sub(a+16, P+16, sub(a, P, 0));
}
void mmpy(UL *a, UL *b, UL *c, UL *P)
{
//printf ("multiplying %08x * %08x\n", a, b);
UL result[32];
int i, j;
memset(result, 0, sizeof(result));
for (i = 31; i >= 0; i--) {
for (j = 31; j >= 0; j--) {
unsigned long mask = 1UL << j;
mshl(result, P);
if (mask & b[i]) {
madd(result, a, P);
}
}
//printf("i: %d, mask: %08x, c: %08x\n", i , mask, c);
}
//printf("result is: %ld, 0x%08x\n", c, c);
memcpy(c, result, sizeof(result));
}
void mexp(UL *a, UL *b, UL *c, UL *P)
{
//printf ("doing a^b mod(P)\n");
UL result[32];
int i, j;
memset(result, 0, sizeof(result));
result[0] = 1;
for (i = 31; i >= 0; i--) {
for (j = 31; j >= 0; j--) {
unsigned long mask = 1UL << j;
mmpy(result, result, result, P);
if (mask & b[i]) {
mmpy(result, a, result, P);
}
}
//printf("i: %d, mask: %08x, c: %08x\n", i , mask, c);
}
//printf("result is: %ld, 0x%08x\n", c, c);
memcpy(c, result, sizeof(result));
}
/* This assumes that dd points to a 2048-bit */
/* dividend and dv points to a 1048-bit */
/* divisor. The high-order half of *dd must */
/* be smaller than *dd for no divide */
/* overflow. The quotient ends up in the low */
/* half of *dd and the remainder in the high */
/* half. WP--10/98 */
void dshl(UL *a)
{
shl(a+48, shl(a+32, shl(a+16, shl(a, 0))));
}
void ddiv(UL *dd, UL *dv)
{
int i;
if(mcmp(dd+32, dv, 32)>0) {
printf("Divide Overflow\n");
exit(0);
}
for(i = 0; i<1024; i++) {
dshl(dd);
if(mcmp(dd+32, dv, 32)>=0) {
sub(dd+48, dv+16, sub(dd+32, dv, 0));
*dd |= 1; /* one quotient bit */
}
}
}
/* This function calculates b mod k where */
/* b is a 1024--bit (32 word) number and k */
/* is less than 2^15. WP--10/02 */
UL rr(UL *b, UL k)
{
int i;
UL m, ans;
m = ((0xffffffff % k) + 1) % k; /* 2^32 mod k */
ans = 0;
for(i = 31; i >= 0; i--) {
ans = (ans*m) % k;
ans = (ans + b[i]) % k;
}
return ans%k;
}
/* This function expects as its second argument a */
/* (pointer to a) string that contains 32 hex words */
/* separated by spaces and/or new line characters, in */
/* big-endian order and it converts those words to */
/* binary and puts them in the array that a points to, */
/* declared "UL a[32];" in little endian sequence, i. e. */
/* the first word in the string goes into b[31] and the */
/* last word in the string goes into b[0]. */
void sget(UL *a, char *b)
{
sscanf(b, "%x %x %x %x %x %x %x %x %x %x %x %x %x %x %x %x "
"%x %x %x %x %x %x %x %x %x %x %x %x %x %x %x %x ",
a+31, a+30, a+29, a+28, a+27, a+26, a+25, a+24,
a+23, a+22, a+21, a+20, a+19, a+18, a+17, a+16,
a+15, a+14, a+13, a+12, a+11, a+10, a+9, a+8,
a+7, a+6, a+5, a+4, a+3, a+2, a+1, a);
}
void sput(char *b, UL *a)
{
int len = sprintf(b, "%08x %08x %08x %08x %08x %08x %08x %08x\n",
a[31], a[30], a[29], a[28], a[27], a[26], a[25], a[24]);
len += sprintf(b + len, "%08x %08x %08x %08x %08x %08x %08x %08x\n",
a[23], a[22], a[21], a[20], a[19], a[18], a[17], a[16]);
len += sprintf(b + len, "%08x %08x %08x %08x %08x %08x %08x %08x\n",
a[15], a[14], a[13], a[12], a[11], a[10], a[9], a[8]);
len += sprintf(b + len, "%08x %08x %08x %08x %08x %08x %08x %08x\n",
a[7], a[6], a[5], a[4], a[3], a[2], a[1], a[0]);
}
double get_time_diff(struct timeval start, struct timeval finish)
{
double f, s;
f = (double)finish.tv_sec;
f += ((double)finish.tv_usec)/1000000.0;
s = (double)start.tv_sec;
s += ((double)start.tv_usec)/1000000.0;
return f - s;
}
