Active Topics
-
Error after installing Leste on sdcard (16)
to Maemo 7 / Leste by t-b - 17 mins ago -
Maemo 20th Anniversary (4)
to Brainstorm by teroyk - 1 day, 3 hrs ago -
Nokia Booklet 3G (RX-75) Drivers (64)
to Alternatives by teroyk - 1 day, 3 hrs ago -
Porting apps to Leste (46)
to Maemo 7 / Leste by teroyk - 3 days, 7 hrs ago - more...
 |
|
2013-07-20
, 10:06
|
|
Posts: 3,404 |
Thanked: 4,474 times |
Joined on Oct 2005
@ Germany
|
#2
|
The algorithm itself is not so complex (university students sometimes implement the RSA algorithm for homework), but it's based on mathematical trap-door function (one-way). Basically you're calculating with huuuuge prime numbers and therefore cannot apply prime factorization to solve the encryption backwards.
__________________
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
|
|
2013-07-20
, 13:14
|
|
Banned |
Posts: 280 |
Thanked: 295 times |
Joined on Apr 2013
@ Romania
|
#3
|
Originally Posted by pycage
Well that was the point, if it's only one way algorithm, so this way, you can only encrypt a file, how can you go back and decrypt it? That was one of the main questions, you use that to encrypt, but sometimes, you need to revert that and decrypt. The software can do the decryption, how can you not back-trace the decryption process?
The algorithm itself is not so complex (university students sometimes implement the RSA algorithm for homework), but it's based on mathematical trap-door function (one-way). Basically you're calculating with huuuuge prime numbers and therefore cannot apply prime factorization to solve the encryption backwards.
|
|
2013-07-20
, 14:35
|
|
Posts: 3,404 |
Thanked: 4,474 times |
Joined on Oct 2005
@ Germany
|
#4
|
You need the key for decryption. Mathematically it's very hard to compute the key, that's why the encryption is secure.
__________________
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
|
|
2013-07-20
, 15:13
|
|
Posts: 3,404 |
Thanked: 4,474 times |
Joined on Oct 2005
@ Germany
|
#5
|
This is the RSA algorithm:
Let the public key E be a pair of numbers (e,n).
Represent your message M as a number satisfying 0 <= M <= n - 1.
If the message is too long, split it up.
Compute the encryption C = E(M) defined as M^e mod n.
Let the private key D be a pair of numbers (d,n).
Compute the decryption D(C) defined as C^d mod n.
e,d, and n are computed as
n = p * q with p and q being huge random secret prime numbers.
Find a huge number d satisfying gcd(d, (p - 1) * (q - 1)) = 1
Compute e being the multiplicative inverse of d in the numbers ring Z_(p - 1) * q - 1), i.e. e * d = 1 (mod(p - 1) * (q - 1))
Example:
p = 47
q = 59
n = p * q = 2773
(p - 1) * (q - 1) = 46 * 58 = 2668
d = 157
-1 * 2668 + 17 * 157 = 1
17 * 157 = 1 + 2668
17 * 157 = 1 mod 2668
Therefore e = 17 is the multiplicative inverse of 157 in the numbers ring Z_2668.
Now in reality, the numbers are larger; hundred of digits or more depending how strong the encryption is.
To break RSA without knowing d, you have to factorise n = p * q. This is currently not practicable for sufficiently large numbers. Therefore it's a trap-door.
Let the public key E be a pair of numbers (e,n).
Represent your message M as a number satisfying 0 <= M <= n - 1.
If the message is too long, split it up.
Compute the encryption C = E(M) defined as M^e mod n.
Let the private key D be a pair of numbers (d,n).
Compute the decryption D(C) defined as C^d mod n.
e,d, and n are computed as
n = p * q with p and q being huge random secret prime numbers.
Find a huge number d satisfying gcd(d, (p - 1) * (q - 1)) = 1
Compute e being the multiplicative inverse of d in the numbers ring Z_(p - 1) * q - 1), i.e. e * d = 1 (mod(p - 1) * (q - 1))
Example:
p = 47
q = 59
n = p * q = 2773
(p - 1) * (q - 1) = 46 * 58 = 2668
d = 157
-1 * 2668 + 17 * 157 = 1
17 * 157 = 1 + 2668
17 * 157 = 1 mod 2668
Therefore e = 17 is the multiplicative inverse of 157 in the numbers ring Z_2668.
Now in reality, the numbers are larger; hundred of digits or more depending how strong the encryption is.
To break RSA without knowing d, you have to factorise n = p * q. This is currently not practicable for sufficiently large numbers. Therefore it's a trap-door.
__________________
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
Tidings - RSS and Podcast aggregator for Jolla - https://github.com/pycage/tidings
Cargo Dock - file/cloud manager for Jolla - https://github.com/pycage/cargodock
|
|
2013-07-21
, 18:15
|
|
Banned |
Posts: 280 |
Thanked: 295 times |
Joined on Apr 2013
@ Romania
|
#6
|
Originally Posted by pycage
Okay. Thank you for your wonderful explaining, I understood it
This is the RSA algorithm:
Let the public key E be a pair of numbers (e,n).
Represent your message M as a number satisfying 0 <= M <= n - 1.
If the message is too long, split it up.
Compute the encryption C = E(M) defined as M^e mod n.
Let the private key D be a pair of numbers (d,n).
Compute the decryption D(C) defined as C^d mod n.
e,d, and n are computed as
n = p * q with p and q being huge random secret prime numbers.
Find a huge number d satisfying gcd(d, (p - 1) * (q - 1)) = 1
Compute e being the multiplicative inverse of d in the numbers ring Z_(p - 1) * q - 1), i.e. e * d = 1 (mod(p - 1) * (q - 1))
Example:
p = 47
q = 59
n = p * q = 2773
(p - 1) * (q - 1) = 46 * 58 = 2668
d = 157
-1 * 2668 + 17 * 157 = 1
17 * 157 = 1 + 2668
17 * 157 = 1 mod 2668
Therefore e = 17 is the multiplicative inverse of 157 in the numbers ring Z_2668.
Now in reality, the numbers are larger; hundred of digits or more depending how strong the encryption is.
To break RSA without knowing d, you have to factorise n = p * q. This is currently not practicable for sufficiently large numbers. Therefore it's a trap-door.
.Now, if we can carry on this tread, find more stuff like this and explain or find out how it actually works, this will grow up in a wonderful thread!
So shall we continue?
Okay, so everyone of you know what those applications do. Now reading the documentation I just quite didn't understand one concept.
The sources are open, so you can see clearly how the software works, even more, you have a very well explained documentation about each and every feature and how it works, BUT not even the creators of these open source projects can't back-trace the application steps and revert the process.
My question is simple, and I want to know your opionion, how do you create such an application that trough multiple randomization steps you can't undo the final output of it.
I just can't understand the basic idea behind those, even tough I can understand the programming.
Here is a simple example:
The second question, now after this simple example, is somehow the algorithm for the final encryption so complex that it would take several, or thousand of years to decrypt. And if so, how do the software knows to generate the same randomization backwards so it can decrypt the file once more, how is it possible that the software can do this and not be back-traced on it's process to decrypt?
Let's start having a discussion on this shall we?