3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Apple did this for diversifying and anonymity as twin diversify $\endgroup$
    – kelalaka
    Jan 11 at 6:18
  • $\begingroup$ @knaccc The problem is described here. You're very welcome to comment on it and make suggestions. $\endgroup$
    – Greendrake
    Jan 11 at 23:25
3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – kelalaka
    Jan 11 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.