Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why does the all 0 public key have a known private key in SR25519 and ED25519?

substrate.stackexchange.com

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#51

Post by doomrobo »

patrakov wrote: post #30
hdevalence wrote: post #24

I’m a coauthor of Ristretto. There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so that the encoding of the identity (zero) element of the group is the all-zero byte string. So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key. This aspect of the encoding makes it very easy to check whethe…

Just out of curiosity: is a similar problem (generate a valid public key that surely nobody including myself can know the private key of) solvable for RSA?

This is a great question. To rephrase: is it possible to come up with an RSA modulus that even you don't know the factorization of?

The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.

At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.

I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#52

Post by [deleted] »

hdevalence wrote: post #36
etna_ramequin wrote: post #32

Earlier quoted context omitted.

Thanks for the layman’s explanation, I didn’t realise something like that was even possible! What are some use cases for using it? Are they all crypto-currency related?

One use case for generating group elements with verifiably unknown discrete logs is for a commitment scheme, like a Pedersen commitment. In a Pedersen commitment, you have two generators, let’s call them G_value and G_blinding. To commit to a value v, you choose a random blinding factor v_blinding and form the commitment C_v as C_v = v * G_value + v_blinding * G_blinding Later, you can publish (v, v_blinding) to open…

[deleted]

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#53

Post by usr1106 »

Retr0id wrote: post #47
anothernewdude wrote: post #42

Earlier quoted context omitted.

Why is an image viewer using PKI?

Did you reply to the wrong comment? Which image viewer?

Naming collision: Ristretto both an elliptic curve concept and a Linux image viewer.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#54

Post by reportgunner »

Jabrov wrote: post #4

Well that made zero sense to me. Can someone ELI16?

It uses math and it uses 0. When you use 0 in math everything becomes 0 after you multiply it. The more you multiply the more 0 it becomes. I bet you have to multiply a lot in cryptography.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#55

Post by oleganza »

franky47 wrote: post #12

Another footgun is that Curve25519 has a cofactor of 8, which may reveal some information about your private key if some high-order points are used [1]. Some curves (eg: Ristretto) were designed to alleviate this problem. [1] https://neilmadden.blog/2020/05/28/whats-the-curve25519-clam...

Ristretto is not a curve, it's a group.

Curve25519 is a _curve_ that implements a non-prime order _group_. Ristretto255 is a prime-order _group_ that uses Curve25519 as an underlying _curve_.

In other words, Ristretto is a pair of encode/decode functions that map points on _curve25519_ to _ristretto group elements_ and vice versa. It's called "ristretto" because it's a restricted (specific to curve25519) version of Mike Hamburg's Decaf format that "reduces amount of coffee/cofactor by 4" for Edwards curves.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#56

Post by oleganza »

reportgunner wrote: post #54
Jabrov wrote: post #4

Well that made zero sense to me. Can someone ELI16?

It uses math and it uses 0. When you use 0 in math everything becomes 0 after you multiply it. The more you multiply the more 0 it becomes. I bet you have to multiply a lot in cryptography.

Math is about precision, so it's generally not a good idea to have something become "more 0" than actually needed. Especially in cryptography.

So here's my advice. If you multiplied too much by zero, you can make it less 0 by dividing a few times by zero. Then maths would be closer to the precise 0 that you were looking for in the first place.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#57

Post by nailer »

hdevalence wrote: post #49
nailer wrote: post #41

Earlier quoted context omitted.

> So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key. Is this sentence a mistake? A private key is a secret key.

I wrote it while waiting to board in the airport, sorry

Its OK it was just like reading ‘car’ and ‘automobile’ in the same sentence and not being quite sure if that was what was actually meant. Otherwise it was a very clear explanation!

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#58

Post by bondarchuk »

hdevalence wrote: post #24

I’m a coauthor of Ristretto. There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so that the encoding of the identity (zero) element of the group is the all-zero byte string. So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key. This aspect of the encoding makes it very easy to check whethe…

Practical solution: just use all ones instead.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#59

Post by less_less »

oleganza wrote: post #55
franky47 wrote: post #12

Another footgun is that Curve25519 has a cofactor of 8, which may reveal some information about your private key if some high-order points are used [1]. Some curves (eg: Ristretto) were designed to alleviate this problem. [1] https://neilmadden.blog/2020/05/28/whats-the-curve25519-clam...

Ristretto is not a curve, it's a group. Curve25519 is a _curve_ that implements a non-prime order _group_. Ristretto255 is a prime-order _group_ that uses Curve25519 as an underlying _curve_. In other words, Ristretto is a pair of encode/decode functions that map points on _curve25519_ to _ristretto group elements_ and vice versa. It's called "ristretto" because it's a restricted (specific to curve25519) version of M…

Oh huh, I was thinking the origin of the name "ristretto" was that espresso concentrates a certain amount of coffee in a small cup, whereas ristretto concentrates it even more: in this case it removes a cofactor of 8 and not just 4.

Re: Why does the all 0 public key have a known private key in SR25519 and ED25519?

#60

Post by oleganza »

less_less wrote: post #59
oleganza wrote: post #55

Earlier quoted context omitted.

Ristretto is not a curve, it's a group. Curve25519 is a _curve_ that implements a non-prime order _group_. Ristretto255 is a prime-order _group_ that uses Curve25519 as an underlying _curve_. In other words, Ristretto is a pair of encode/decode functions that map points on _curve25519_ to _ristretto group elements_ and vice versa. It's called "ristretto" because it's a restricted (specific to curve25519) version of M…

Oh huh, I was thinking the origin of the name "ristretto" was that espresso concentrates a certain amount of coffee in a small cup, whereas ristretto concentrates it even more: in this case it removes a cofactor of 8 and not just 4.

Ristretto is a restricted form of Decaf, that is, specific to curve25519 and deals with a sign choice, while Decaf is generic for all cofactor-4 Edwards curves.

In other words, the joke around coffee takes a 90º turn with Ristretto because our first application was Bulletproofs where you need (among other things) a lot of orthogonal generator points.

Post reply on HN