2
$\begingroup$

Let's say we will choose some 256-bit random $b$ and we will find the smallest $d$ such that:

$\frac {2^{d}-1}{b} = s$

Now compute $z \equiv s \pmod{2^{128}}$. If I will give you only $z$ - is it possible to compute $b$ in some acceptable time? Is it hard problem? Do we know some algorithm to compute it? Is it save enough to use $z$ as a public key and $b$ as a private key?

EDIT:

I made one mistake, $z$ should be compute in another way - just take $s$ and cut all bits except $128$ least significant. So $z$ is composed of $128$ least significant bits of $s$. It does not change much, probably.

Improve this question
$\endgroup$
4
  • $\begingroup$ Just as a side comment, by taking $z \equiv s \mod(2^{128})$, you are ignoring 127 bits (the LSBs) of $s$. Are you aware of that in your question? $\endgroup$ – Binou Aug 25 '20 at 5:56
  • 2
    $\begingroup$ Isn't one ignoring only the most significant bits? $\endgroup$ – asd Aug 25 '20 at 7:19
  • $\begingroup$ Binou - yes, it is just about removing bits. As you can see, I made a mistake and I was thinking about removing most significant bits. $\endgroup$ – Tom Aug 25 '20 at 15:15
  • $\begingroup$ Tom, accepting the answers if they satisfy your question is important part of this community so that visitors can decide that there is at least one satisfactory answer. $\endgroup$ – kelalaka Aug 28 '20 at 20:13
3
$\begingroup$

We know that $b$ is 256-bit number with

$$2^d - 1 = b\cdot s$$ and

$$z \equiv s \pmod{2^{128}}$$ use the modulo knowledge

$$z = s + k\cdot 2^{128}$$ for some $k \in \mathbb{Z}$ then

$$s = z - k\cdot 2^{128}$$ combine

$$2^d - 1 = b\cdot (z - k\cdot 2^{128})$$

$$2^d - 1 = b\cdot z - b \cdot k\cdot 2^{128}$$

take modulo $2^{128}$

$$ -1 \equiv b\cdot z \pmod{2^{128}}$$

Therefore we learned 128-bit information about $s$ with simple arithmetic. It is not a good way to hide the private key.

Improve this answer
$\endgroup$
2
  • $\begingroup$ We learned 128-bit information about $s$ with simple arithmetic - I was aware that we have this information. But what next? Let's say $s$ is $192$-bit long. We still have to guess $64$ bits. Maybe if $s$ is not long, we can do it fast, but what if we will choose even bigger $s$. Let's say $s$ will be always at least $256$-bit long (maybe then we have to increase $b$) and we know only $128$ bits of $s$. $\endgroup$ – Tom Aug 25 '20 at 15:23
  • 2
    $\begingroup$ In cryptography we compare by the brute force. The $s$ has 256-bit space and with a simple arithmetic we can learn information about half of it. That is a total break and your system now provides only 128-bit security. Now one can go and say, as your argument, with 256 bit we provide at most 128 bit security. I, however, don't like it. This is not comparable to AES-128's theoretical security against quantum attack. $\endgroup$ – kelalaka Aug 25 '20 at 15:30

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.