 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
Posted: |
Jun 14, 2018 - 8:33 AM
|
|
|
|
By: |
Jehannum
(Member)
|
PUBLIC KEY CRYPTOGRAPHY
Is there a way for someone to encode their messages to you so that only you can read them? You could of course share an encryption key but what if it was intercepted by a third party, say a hacker? Your messages could then be read by anyone with the key.
Is there a way to keep messages secure even if the key is known? It turns out there is – public key cryptography. With this method you must generate two keys. One is the public key which you send to the person with whom you want to communicate securely. It allows them to encrypt their messages to you. The clever part is that it’s a one-way key: it can’t be applied in reverse to decrypt the messages. Only you have access to the private key which can decrypt the messages. You keep this to yourself, secret and secure.
So far, so good. But if you try to think of how to actually implement this system you will realise how difficult it is to find a “one-way” operation which can encrypt but not decrypt messages. After all, it’s easy to reverse most mathematical operations. In fact, the full method wasn’t invented until the 1970s although it relies on mathematics discovered many years before.
To understand the method, you need to know a little of the mathematics used. There is a branch of arithmetic called modular arithmetic. We use modular arithmetic every day without even knowing it if we use a twelve-hour clock.
For example, if it’s eight o’clock now, what time will it be in six hours? 8 + 6 = 14. Fourteen o’clock? No – because when we go past twelve we start again. The correct answer is of course two o’clock. What we are doing here is in fact modular arithmetic with a modulus of 12.
In modular arithmetic we can say things like “thirteen hours is equivalent to one hour (on a twelve-hour clock)”. We would write this symbolically as:
13 = 1 (mod 12)
Note that this equivalence between 13 and 1 can be thought of as saying that the remainder of 13 ÷ 12 is the same as the remainder of 1 ÷ 12.
One way that modular arithmetic is useful is that it allows us to perform operations on a number without it tending towards infinity. It means that numbers never get bigger than a certain size, just like the hours on a clock never go above twelve.
Of course, to be secure, cryptography uses a modulus much bigger than 12. In the widely-used RSA encryption method the modulus is the product of two very large prime numbers (which have more than a hundred digits each and which are unequal in length).
The public key consists of two numbers, n (the modulus) and e (a number chosen to give certain results which we’ll see more about later).
Computers represent text as numbers. For example, in the commonly-used ASCII code the letter “A” is stored as the number 65; “B” = 66 and so on. This makes it easy for computers to perform mathematical operations on messages.
An encrypted message C is generated from an unencrypted message M by raising it to the power e (under the modulus of n):
C = M^e (mod n)
The private key consists of two numbers, n (the same n as in the public key) and d (a different number which was chosen together with e when the keys were generated).
The message recipient decrypts C like this:
M = C^d (mod n)
So how are d and e chosen? This is where the maths gets a little tricky. The first thing we note is that if we apply encryption and then decryption to our message we must end up with the original message M. In mathematical terms this is an identity operation. That is, we require e and d to be chosen such that:
(M^e)^d = M^(e · d) = M (mod n)
Note: if you have a number M to the power e and then raise that to the power d, it’s the same as M to the power (e · d). Here we use the symbol · to denote multiplication.
The mathematician Euler discovered that the following equivalence holds when M and n are coprime (i.e. when they have no common factors):
M^f(n) = 1 (mod n)
f(n) is called the totient function. For our purposes it suffices to say that if p is prime, f(p) = (p – 1). For example, f (13) = 12.
It follows that we can multiply the left-hand side by any integral power k and Euler’s equivalence will still hold:
M^(k · f(n)) = 1 (mod n)
Multiplying both sides by M gives:
M^(k · f(n) + 1) = M (mod n)
We now see that this can give us a way to find d and e:
M^(k · f(n) + 1) = M^(d · e) (mod n)
So: d · e = k · f(n) + 1
For n, the product of primes p and q, f(n) = (p – 1) (q – 1).
So: d · e = k · (p – 1) (q – 1) + 1
To decrypt the message without the private key, you would need to work out d from the public key (n and e). To do this you’d need to find the prime factors (p and q) of n. Prime factorisation of large numbers is very difficult. The only methods known are little better than trial-and-error. This means that for large n it will take even the fastest computers billions of years to find the prime factors. Anyone intercepting a message encrypted this way will not be able to decrypt it in a feasible amount of time - even if they have the public key.
Because of its high computational overheads, public key cryptography is not normally used to send whole messages. Instead, it’s used to share a private "single session" key which allows faster encryption and decryption methods.
Worked example
We will encrypt the message, “HI”.
First, we generate the keys. We choose the primes p = 5 and q = 11, so n = 55 and:
f(n) = (5 – 1) (11 – 1) = 40
To find d and e we use the relation we saw earlier:
d · e = k · f(n) + 1 = k · 40 + 1
The product of d and e can thus be equal to 41, 81, 121, 161, etc. We choose 161 because it has two distinct prime factors, e = 7 and d = 23.
The public key {n, e} = {55, 7}, and the private key {n, d} = {55, 23}.
The message “HI” is composed of two characters (ASCII codes 72 and 73). To simplify computations we’ll subtract 65 from these so that “A” starts at 1. The message becomes M = {8, 9}. The encryption operation C = M^e (mod n) is:
{8^7 (mod 55), 9^7 (mod 55)}
= {2, 4}
The decryption operation M = C^d (mod n) is:
{2^23 (mod 55), 4^23 (mod 55)}
= {8, 9}
And we are back at the original message.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Posted: |
Jun 16, 2018 - 8:29 AM
|
|
|
|
By: |
OnyaBirri
(Member)
|
PUBLIC KEY CRYPTOGRAPHY
Is there a way for someone to encode their messages to you so that only you can read them? You could of course share an encryption key but what if it was intercepted by a third party, say a hacker? Your messages could then be read by anyone with the key.
Is there a way to keep messages secure even if the key is known? It turns out there is – public key cryptography. With this method you must generate two keys. One is the public key which you send to the person with whom you want to communicate securely. It allows them to encrypt their messages to you. The clever part is that it’s a one-way key: it can’t be applied in reverse to decrypt the messages. Only you have access to the private key which can decrypt the messages. You keep this to yourself, secret and secure.
So far, so good. But if you try to think of how to actually implement this system you will realise how difficult it is to find a “one-way” operation which can encrypt but not decrypt messages. After all, it’s easy to reverse most mathematical operations. In fact, the full method wasn’t invented until the 1970s although it relies on mathematics discovered many years before.
To understand the method, you need to know a little of the mathematics used. There is a branch of arithmetic called modular arithmetic. We use modular arithmetic every day without even knowing it if we use a twelve-hour clock.
For example, if it’s eight o’clock now, what time will it be in six hours? 8 + 6 = 14. Fourteen o’clock? No – because when we go past twelve we start again. The correct answer is of course two o’clock. What we are doing here is in fact modular arithmetic with a modulus of 12.
In modular arithmetic we can say things like “thirteen hours is equivalent to one hour (on a twelve-hour clock)”. We would write this symbolically as:
13 = 1 (mod 12)
Note that this equivalence between 13 and 1 can be thought of as saying that the remainder of 13 ÷ 12 is the same as the remainder of 1 ÷ 12.
One way that modular arithmetic is useful is that it allows us to perform operations on a number without it tending towards infinity. It means that numbers never get bigger than a certain size, just like the hours on a clock never go above twelve.
Of course, to be secure, cryptography uses a modulus much bigger than 12. In the widely-used RSA encryption method the modulus is the product of two very large prime numbers (which have more than a hundred digits each and which are unequal in length).
The public key consists of two numbers, n (the modulus) and e (a number chosen to give certain results which we’ll see more about later).
Computers represent text as numbers. For example, in the commonly-used ASCII code the letter “A” is stored as the number 65; “B” = 66 and so on. This makes it easy for computers to perform mathematical operations on messages.
An encrypted message C is generated from an unencrypted message M by raising it to the power e (under the modulus of n):
C = M^e (mod n)
The private key consists of two numbers, n (the same n as in the public key) and d (a different number which was chosen together with e when the keys were generated).
The message recipient decrypts C like this:
M = C^d (mod n)
So how are d and e chosen? This is where the maths gets a little tricky. The first thing we note is that if we apply encryption and then decryption to our message we must end up with the original message M. In mathematical terms this is an identity operation. That is, we require e and d to be chosen such that:
(M^e)^d = M^(e · d) = M (mod n)
Note: if you have a number M to the power e and then raise that to the power d, it’s the same as M to the power (e · d). Here we use the symbol · to denote multiplication.
The mathematician Euler discovered that the following equivalence holds when M and n are coprime (i.e. when they have no common factors):
M^f(n) = 1 (mod n)
f(n) is called the totient function. For our purposes it suffices to say that if p is prime, f(p) = (p – 1). For example, f (13) = 12.
It follows that we can multiply the left-hand side by any integral power k and Euler’s equivalence will still hold:
M^(k · f(n)) = 1 (mod n)
Multiplying both sides by M gives:
M^(k · f(n) + 1) = M (mod n)
We now see that this can give us a way to find d and e:
M^(k · f(n) + 1) = M^(d · e) (mod n)
So: d · e = k · f(n) + 1
For n, the product of primes p and q, f(n) = (p – 1) (q – 1).
So: d · e = k · (p – 1) (q – 1) + 1
To decrypt the message without the private key, you would need to work out d from the public key (n and e). To do this you’d need to find the prime factors (p and q) of n. Prime factorisation of large numbers is very difficult. The only methods known are little better than trial-and-error. This means that for large n it will take even the fastest computers billions of years to find the prime factors. Anyone intercepting a message encrypted this way will not be able to decrypt it in a feasible amount of time - even if they have the public key.
Because of its high computational overheads, public key cryptography is not normally used to send whole messages. Instead, it’s used to share a private "single session" key which allows faster encryption and decryption methods.
Worked example
We will encrypt the message, “HI”.
First, we generate the keys. We choose the primes p = 5 and q = 11, so n = 55 and:
f(n) = (5 – 1) (11 – 1) = 40
To find d and e we use the relation we saw earlier:
d · e = k · f(n) + 1 = k · 40 + 1
The product of d and e can thus be equal to 41, 81, 121, 161, etc. We choose 161 because it has two distinct prime factors, e = 7 and d = 23.
The public key {n, e} = {55, 7}, and the private key {n, d} = {55, 23}.
The message “HI” is composed of two characters (ASCII codes 72 and 73). To simplify computations we’ll subtract 65 from these so that “A” starts at 1. The message becomes M = {8, 9}. The encryption operation C = M^e (mod n) is:
{8^7 (mod 55), 9^7 (mod 55)}
= {2, 4}
The decryption operation M = C^d (mod n) is:
{2^23 (mod 55), 4^23 (mod 55)}
= {8, 9}
And we are back at the original message.
Thanks for clarifying.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
