Join Log in
Score:3
Greendrake avatar Crypto

It is possible to prove that two private keys are related?

in flag
Greendrake

Say Alice owns two keypairs: ($Pub_1$, $Priv_1$) and ($Pub_2$, $Priv_2$).

The pair ($Pub_1$, $Priv_1$) is pretty mundane.

$Priv_2$ was intentionally created by Alice by concatenating $Priv_1$ and the word "banana" (and then she derived $Pub_2$ out of $Priv_2$ the usual way).

Bob knows the public keys.

In any asymmetric key algorithm, is it possible for Alice to prove that $Priv_2$ = $Priv_1$ + "banana"? — without revealing the private keys?

605
0 + 0
kelalaka avatar
in flag
kelalaka
Apple did this for diversifying and anonymity as [twin diversify](https://crypto.stackexchange.com/q/86073/18298)
0
Reply
Greendrake avatar
in flag
Greendrake
@knaccc The problem is described [here](https://greendrake.info/publications/trusted-anon-identity). You're very welcome to comment on it and make suggestions.
0
Reply
Score:3
knaccc avatar Crypto
es flag
knaccc

Let's say you use Curve25519, which has a well-known generator point $G$ which forms a cyclic group of size $\ell$. Valid scalars (private keys) are usually expressed as unsigned little-endian 32-byte sequences.

The ASCII bytes of $\texttt{banana}$ interpreted as a little-endian number is $107126708920674$.

If you append the ASCII bytes of $\texttt{banana}$ to a 32-byte (256-bit) little-endian private key, what you are mathematically doing is adding $x$ where $x = 107126708920674 \cdot 2^{256}$. Because this private key will exceed the group size $\ell$, an elliptic curve library will only accept it as a private key after it has been reduced $mod\ \ell$.

Therefore the concatenation with $\texttt{banana}$ means you have $priv_2 = priv_1 + x\ mod\ \ell$.

Anyone can easily observe that $pub_2 == pub_1 + x \cdot G$, which could only have happened if you had either added $x$ to $priv_1$, or added $x + n \cdot \ell$ for some value of $n$.

0 + 0
kelalaka avatar
in flag
kelalaka
First, a word is not a good randomizer. 2. Since ECDSA doesn't hash the private key as EdDSA, Alice can create a signature with the other key by only using the word banana ( need some real validation other than my mind). I couldn't see a great threat, however, one should be very careful while using this simple relation. The Twin Diversify, on the other hand, provides better relations...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.