2
$\begingroup$

This is part of a question I asked on information security stack exchange which might be better suited here.

I'm looking to implement a script in an ad-hoc scripting language with no crypto libraries, which can tell whether or not a password is valid without revealing the password. I also need the password to be as short as possible without being crackable.

One possibility is to store a large semiprime and have the password be a factor. But semiprimes need to have factors which are hundreds of bits long to be difficult to crack. I'd rather the password be around 64 bits. I'm considering storing a 1024-bit semiprime along with 448 bits of one of its 512-bit factors, and have the other 64 bits be the password, but I have no idea if this is crackable.

So my question is: If a 1024-bit semiprime is stored along with the first 448 bits of one of its 512-bit factors, can the remaining 64 bits of that factor be feasibly found?

Improve this question
$\endgroup$
10
  • $\begingroup$ Are you assuming that the attacker (or your friend, in this case) will reverse engineer the application, but not modify it? $\endgroup$
    – mikeazo
    Commented Aug 11, 2016 at 17:24
  • 1
    $\begingroup$ Personally I think the bit about whether or not leaking 448 bits of a 512-bit factor of a semiprime would be a pretty good question on here. The question about "is there another way" might be better left on Security.SE. $\endgroup$
    – mikeazo
    Commented Aug 11, 2016 at 17:32
  • 1
    $\begingroup$ I was looking for it, and finally found it, I think your first question about factoring a semiprime given some bits of one of the factors has already been explored here. Though what is not clear to me is how those answer apply since you don't have an $e$. $\endgroup$
    – mikeazo
    Commented Aug 11, 2016 at 17:40
  • 1
    $\begingroup$ @cardboard_box, I'm posting a different option on Security.SE for you. $\endgroup$
    – mikeazo
    Commented Aug 11, 2016 at 17:50
  • 1
    $\begingroup$ Just to clear things up, I'll close this as a duplicate of the other, then update my answer on the other. The results of the Coppersmith theorem still apply. The size of $e$ only matters when given bits of $d$. $\endgroup$
    – mikeazo
    Commented Aug 11, 2016 at 18:24

0

Reset to default

Browse other questions tagged or ask your own question.