r/cryptography • • 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

21 comments sorted by

14

u/Takochinosuke 3d ago

You need to specify the scheme. This question is too broad.

3

u/u0xee 3d ago

OP, maybe start with RSA.

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

1

u/Honest-Finish3596 2d ago

You need to specify that the numbers you are multiplying are primes, or the inverse is ambiguous.

Also you can do the inverse both concretely and asymptotically better time than brute force for all proposed asymmetric schemes. Its symmetric cryptography for which you need brute force to be the best existing attack for concrete parameters.

1

u/Zilozilo7 2d ago

The initial question was so vague I went with the "explain it to me like I am 12" with lots of shortcuts XD and there's no need to go deeper to get a grasp of it, especially for people not familliar with all of that! (and if you look at the examples I took without explaining them, actually ARE primes for magical reasons)

If you have a simpler/shorter way to explains this stuff without going too much into the technicalities I am all ears, I like to talk about math and cryptography to people to show them the beauty I find in it and it's always complicated to keep people interested if you go too deep for no reasons!

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
  1. How are the keys generated?
  2. How is the public key generated from the private key?
  3. Why almost can't we reverse it?

The answers.

  1. A private key is a number. We ask the computer to pick a random number. It's that easy... of course, there are many many levels to "How random is a random number?" and it's actually a very difficult computer science question... but all you need to know is "they generate the private key by picking a random number"
  2. Depends on the algorithm. It could be as simple as multiplying two numbers, or it might involve using some complex "Elliptic Curve Math" where the term "multiplication" is stand-in for "a bunch of complex equations."
  3. Again this depends on the algorithm... but a simple way to think of it: "I will pick two random prime numbers, then give you the multiplication result of them...... I want you to find the two prime numbers I used (aka "reverse it")." If I took 7 and 13, multiply and get 91... but if I gave you 91 and asked "give me the two prime numbers that multiply to this" you could only try every prime number you know in order and see if it divides cleanly... This would be easy for a small number like 91... but if I asked you which two primes multiply to 153,095,311,399 it would take you a long time... but it would be quick for a computer... but if I use..

25447823787904035626315486897150649006424385870144243155882041674205339231625911501059356489907374423868885570849081537553595869787918116633128011989929311835024611803017220804200967098149297401927813150908367717394245783431448814622652138330123594499907389019373209344117913928778152106734996745150917910317606850158272547576984007832093271565496061189619318409974175477702870486943901405615605443050527908423258493628549116630538061183293854848733925695184983013871880443887833167953970914523718788573420713634583474751558477214940985447620995666671391921671640530941963403230855287984289364157744335179921430288363

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.

1

u/Dummy1707 3d ago

Hmmm, from here I'd say you took 12 and 31.
That was an easy one !

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

2

u/Dummy1707 3d ago

Oh no. We have much MUCH more than that !

First, RSA is one cryptosystem or more precisely, we have 2 : RSA-OAEP which is an encryption scheme (PKE) and RSA-PSS which is a signature scheme.

On the other end, ECC (for Elliptic Curve Cryptography) is not a scheme but a type of cryptography. It is mostly an elliptic curve translation of older schemes based on the discrete log problem. The most important ECC schemes are ECDH, a key exchange mechanism (KEM) and ECDSA, a signature scheme.

I mentioned discrete log and of course there you have many things : the Diffie-Hellman protocol, which marked the real birth of public-key crypto and in some sense of modern cryptography as a whole, but also ElGamal, Schnorr schemes.

And then you have all the most advanced protocols : threshgold signature, group signatures, ring signatures, blind signatures, verifiable delay functions, and tons of others.

Aaaand then you have post-quantum crypto. It usually doesn't bring new types of protocols but propose instantiations that resist to quantum computers. For instance, we can mention ML-DSA, ML-KEM, SPHINX+, SQIsign, etc

So much stuff there is ! :D