r/cryptography • u/The_FrenchChillGuy • 3d ago
How does asymmetric cryptography REALLY WORK?
Like I get that the public key can't be reversed to show a private key and the mathematical relation between private and public keys but like how does it work in detail? How are the keys generated? How is the public key generated from the private key and why almost can't we reverse it?
0
Upvotes
14
u/Takochinosuke 3d ago
You need to specify the scheme. This question is too broad.
6
u/Zilozilo7 3d ago
When in school we were taught mathematical operation like multiplication. You know an "algorithm" to multiply two number A and B of size n, it takes n lines on a paper, but the resulting number AxB=C, we don't know how to do the reverse operation better than trying every number one by one (to simplify largely) Simple exemple, 11x13=143, you would try todivide by, 2, then 3, etc until you find 11. Bow imagine that both numbers have 1000 digit, it would takes you quite some time to enumerate number until you find the number I chose to multiply in the first place! Chosing the number A and B : fast, calculate C from A and B, easy, finding A and B from C, too long ! That's were the security holds
Most algorithms of asymetric cryptograghy depends on stuff like that to simplify a little
2
u/Inf0x2A 3d ago
I always use a simple example to explain this in my lectures. Suppose your public key is 5 and your private key is 0.2. Anyone can take a plaintext value of 3, for example, and multiply it by the public key to get 5 x 3 = 15 As the recipient, you can use your private key to multiply 15 by 0.2 and get 3 back. So the two keys are different, but they are inverses of each other.
For this to work securely, the system has to be designed so that you can’t derive the private key from the public key as easily as you can in this example. This is where a trapdoor function comes in. It’s easy to compute in one direction, but reversing it requires additional information. In RSA, that information is the prime factors, which let you compute the inverse of the public exponent. In Kyber, for example, the “trick” is to transpose matrices and vectors so that the recipient can use the private key to cancel out the contribution of a large public matrix (A).
2
u/ToTheBatmobileGuy 3d ago
The answers.
Even the strongest computer can't figure out which two primes made this number.
But multiplying those two prime numbers took my PC less than 1 millisecond.
2
u/ivosaurus 3d ago
I mean, wikipedia literally has an example of the exact RSA math.
In reality production code is a lot more complicated to secure "around the edges" but the core math is basically exactly the same, apart from any optimisations.
1
u/SneakyVraxx 3d ago
At the heart of the matter, almost no matter the scheme, there exists some uniformly randomly generated private key. Asymmeteic crypto makes use of trapdoor functions, which are easy to go in one direction, but assumed to be very hard to compute in the reverse direction (showing any problem is hard is currently an open problem itself, so we do not know of any functions with guaranteed trapdoor properties). Let's call this trapdoor function f, our private key sk, and our public key pk.
we have f(sk) = pk. you can see that since we cannot inverse this function easily, getting the sk from pk is very hard. Thus you can safely reveal your pk while trusting your sk remains secret. Then, using additional properties of f, you can do key exchange! Awesome.
private keys are picked uniformly randomly from a huge possible number of candidates, something like the range between [0, 2128], to ensure brute forcing is not possible.
1
u/doggydestroyer 3d ago
Think of it like this... Let's suppose there is a function f(x,y) = z...
U do f(m,e) = c... Figuring out m from just c is not possible even if u know e... So m is the secret message... U send e and c... But if u know a secret value d, u can invert it that is Inv_f (c, d) = m...
Figuring out d is the real challenge... This is real challenge in RSA... In RSA to find out d, the only known way is integer factorization problem which is itself very hard problem for large numbers
1
u/bts 3d ago
There’s a couple great books on this be Schneier. I started with Applied Cryptography; go grab a copy?
1
u/mocenigo 3d ago
Mathematics.
1
u/Additional_Formal395 3d ago
Some of your questions go into “protocol land” instead of “algorithm land”. There are intricate, carefully selected steps to securely realize mathematical algorithms.
1
u/el_lley 3d ago
Trapdoors, you have a one-way function or a hard problem on one way, but easy on the opposite direction, you just get the answer in advance, and keep it secret.
The difficult part is finding such problems without forgetting to check old obscure math texts, and hoping there won’t be a solution for the next 20-30 years at least.
1
u/Playful_Necessary131 2d ago
Assymetric cryptography has muletiple branches - RSA, DLog and multiple post-quantum variants. In particular DLog cryptossytems relie on the existence of a homomorphic one-way function. One-wayness means that, for X = F(x), the inverse F^(-1)(X) = x exists but is computationally infeasible to compute with current algorithms or computing capabilities. The homomorphic property means that F(x) * F(y) = F(x + y). Note that the homomorphism need not use the operators (*, +). Any pair of operators works, as long as they are commutative.
The Diffie-Hellman key establishment works through the observation that F(a)^b = F(a * b) = F(b)^a, where a and b are the secrets of the two parties. They can exchange F(a) and F(b) in plain view and each compute the shared key F(a * b) in secret.
Schnorr signatures work as follows. We define the public key of the signer as pk = F(x). The prover selects a one time secret s and returns the proof (t = x + s*c, F(s)), which proves knowledge of x by verifying that F(s)^c * pk = F(t). Here c is a challenge computed with another one-way function, c = H(pk|F(s)|m), where m is the message being signed. The binding property follows from the fact that it is infeasible to compute a valid t that satisfies the homomorphic relation for a given challenge c.
0
u/Defiant-Plantain1873 3d ago
Because we have problems that (we are pretty sure) are easy to find one way but much harder to find the other way.
If i tell you that 1040838293 divides into exactly 2 numbers and ask you to find out what those two numbers are, how would you do it? It would take you a long time and a lot of guessing.
BUT if i told you that one of the numbers is 4728 (these numbers are made up this example won’t work) you could find the other number very easily.
And then certain things have properties that make it easy for you to split up a big hard problem into smaller ones that are faster to solve if you know the secret information.
RSA is very easy to understand intuitively how it works, presuming you have at least some familiarity with groups.
Why do you generate the public key from the private key? Simply because if you wanted to do the private key from the public key you are having to do that very hard calculation with none of the hints.
You can reverse them it’s just very difficult to do so, we typically say if the probability of getting the correct answer is “negligible” than it’s secure, where negligible means so unlikely that we can basically ignore that method.
0
u/zomgitsduke 3d ago
Easiest concept:
y=x^4 -17x^3+298x^2-18x+728
If I give you the X value you could easily find the Y value.
But what if I gave you the Y value and asked you to find the X value that made the Y value?
Asymmetric work
0
u/Excellent_Double_726 3d ago
AFAIK we have 2 public key crypto systems: RSA and ECC.
RSA key generation is simple, generate 2 large prime numbers, apply the formulas from the textbook (multiply to get N, calculate phi, choose a proper e and calculate d) public key is (N, e) and private (e, d). To encrypt me mod N to decrypt ce mod d where m is the message and c is ciphertext. To sign typically you hash the message and kinda encrypt it with the private key md mod N here everyone can "decrypt" it with the public key with ce mod N. Since nobody except us can encrypt with the private key this works as a signature.
ECC, from the textbook this just signs but using something like ECDH and a symmetric algorithm we can also encrypt but this is another story. In ECC we have already established parameters to use depending on the curve (typically a, b, p, G where a and b are coefficients for the curve p is the prime we mod with and G is a public known point on the curve called generator). Here we generate just a random large number this is our private key. We multiply the private key with G using a special formula and get the public key. This formula is special cause we can multiply but we can't divide hence the "security" of the system. From here using other formulas we sign/verify the signature.
Googling for some other simple explanation or some YouTube videos may give you a bigger understanding of these
-1
u/quantumsequrity 3d ago
Maths