Encryption (encryption, encoding). The Encryption is the process of re illegible information considered important. Once encrypted the information can only be read by applying a key.
is a security measure that is used to store or transfer sensitive information should not be accessible to third parties. Can be passwords, credit card numbers, private conversations, etc.
I recently read about a method for encrypting information that is very interesting, was created in 1978 and is called RSA, which stands for its creators: Rivest, Shamir and Adleman, is based on the difficulty of factoring large numbers prime numbers, for example, it is easy multiply 2 primes for a third but it is difficult from the third to get his 2 prime factors. In fact this is the best encryption method used there and banks, government institutions, etc. A bank of Monterrey, NL using this system supplied then by RSA, The Security Division of EMC is Banorte :
Most prime numbers used in RSA encryption are 250 digits or more, ie for more because security is later factored a prime number is the bigger. Theoretically raw 250-digit numbers takes millions of years to factor.
it works exactly
turns out that:
$ c \\ equiv m ^ {e} \\ mod \\ n $
$ m \\ equiv c ^ {d} \\ mod \\ n $
If and only if $ n = pq $, q are primes
$ 1 \u0026lt;e \u0026lt;\\ phi (n) $ and $ gcd (e, \\ phi (n)) = 1 $, with $ \\ phi (n) = (p- 1) (q-1) $
and meets a $ d \\ equiv 1 \\ mod \\ n $
m c would be a numeric message against encrypted part.
and serious public key to encrypt d the private key to decrypt.
Note: phi (n) is the Euler function. Procedure
- two numbers p and q are sought to be cousins.
- n are obtained by multiplying p and q, and phi (n) by multiplying (p-1) and (q-1).
- and is looking for a number that has no common divisors phi (n), which divides phi (n) +1 no residue.
- d It is the division phi (n) +1 from e.
- now have everything and be the public key (e, n) while the private is (d), like the rest of the numbers (p, q, phi (n)) are not going to need, can be destroyed for safety.
Example Suppose we choose:
$ p = 11, \\ q = $ 23, two small primes ideals for our example.
Then calculate n: $ n = pq = 253, $
compute phi (n) $ \\ phi (n) = (p-1) (q-1) = (11-1) (23-1) = 220 $
And e: $ $ 1 \u0026lt;e \u0026lt;\\ phi (n) = 220 \\ and \\ gcd (e, 220) = 1 $ $.
it meets a number is 13: $ $ 1 \u0026lt;13 \u0026lt;\\ phi (n) = 220 \\ and \\ gcd (13, 220) = 1 $ $
Now d is the division of phi (n) +1 between and $ \\ frac {221} {13} = 17 $. We note that we have: $ (17) (13) \\ equiv 1 \\ mod \\ $ 253, or is, phi (n) +1 can be divided by and with residue 0.
Check:
With the message: 11
$ c = 11 ^ {13} \\ mod \\ 253 = $ 132
$ m = 132 ^ {17} \\ mod \\ 253 = $ 11
Another example
clearer Another example would be:
$ p = 3, \\ q = $ 11
$ n = $ 33
$ \\ phi n = (3-1) (11-1) = 20 $
$ e = $ 7 because it complies with 1
$ d = \\ frac {\\ phi (n) +1} {e} = \\ frac { 21} {7} = $ 3
Check: With the message
m = 2
$ c = m ^ {e} \\ mod \\ n = 2 ^ {7} \\ mod \\ \\ 33 = 128 \\ mod \\ 33 = $ 29
$ m = c ^ {d} \\ mod \\ n = 29 ^ {3} \\ mod \\ 33 = 24 389 \\ mod \\ 33 = $ 2
We can see that if we introduce the message m = 2 is encrypted in c = 29 and can be decrypted with the private key d. Now with our keys can encrypt and decrypt any message Numeric longer be.
Note that if you are making very large exponentiation operations, you must use the binary algorithm potentiation saving operations.
Some ways to convert text to numbers is to apply a numerical key for parties or simply making ASCII values \u200b\u200b(although this is not so sure). More information
http://www.rsa.com/
http://www.tagoror.com/enciclopedia/es/wikipedia/f/fu/funcion_phi_de_euler.html
http://boards5.melodysoft.com/canalingenio/la-funcion-phi-de-euler-225.html
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rsa . html
Now I will show the pseudocode I'm doing, not finished but I get the idea what I do to implement it.
/ * Pseudocode for encryption, RSA method * / # include
< stdio.h >
#include < time.h >
#define p long 47
#define q long 13
long p, q, n, h, e, d, m;
char M[4000];
long a[3], b[3], m[3], res;
n();
h();
e();
d();
string();
ps();
encrypt();
decrypt();
show-string();
main()
{
n();
h();
e();
d();
put-string();
ps(M)
encrypt(m);
decrypt(c);
ps(m);
show-string(M);
getch();
}
n()
{
//Elegir 2 primos (p y q)
n=p*q;
}
h()
{
//Funcion phi Euler
h=(p-1)*(q-1);
}
e()
{
//e
e=(5*h)/8;
fac[0]=e;
fac[1]=h;
gcd();
while (fac[1]!=1&&)
{e + +;
gcd ();}
} d ( )
{/ / Extended Euclidean Algorithm to calculate
/ / the modulo multiplicative inverse: e (mod h)
a [1] = 1;
b [1] = 0;
m [1] = e;
a [2] = 0;
b [2] = 1;
m [2] = h;
res = e-(h * m [2]);
while (m [2]! = 1) {
/ / Run the values
a [0] = a [1];
a [1] = a [2];
, b [0] = b [1];
b [1] = b [2];
m [0] = m [1];
m [1] = m [2];
/ / Calculate last
values \u200b\u200bof [ 2] = a [0] - (a [1] * res);
b [2] = b [0] - (b [1] * res);
m [2] = m [0] - (m [1] * res);}
d = a [2];}
string
() {
printf ("Enter the message you want to encrypt: \\ n");
scanf ("% s", M);}
ps (char x) {
/ / Convert string to numbers or vice versa
if (isalfa (x)) {
tonumber
m = (x);
return m;
} else {
M=toalfa(x);
return M;
}
}
long encrypt(long)
{
c=pow(m, e) mod n;
return c;
}
long decrypt(long)
{
m=pow(c, d) mod n;
return m;
}
show-string()
{
printf("%s", M);
}
gcd()
{
//Algoritmo euclidiano
fac[0]=e;
fac[1]=h;
fac [2] = factor [0]% fac [1];
while (fac [2]! = 0) {
fac
[0] = fac [1];
factors [1] = factor [2];
fac [2] = factor [0] % fac [1];
}}
pseudocode and will continue improving Improve public information contained herein. They can shop around from time to time to see the progress. Also add more links to information if they are unsure how to get all the numbers for the keys, is supposed to use certain methods of factorization and the Euclidean algorithm we learned last class in room but for lack of time not show you here.
Updated May 18, 2010: I corrected a few important things and add one more example.
Updated May 21, 2010: Using binary algorithm potentiation saving operations.
0 comments:
Post a Comment