Skip to main content
Information Security

Return to Answer

added 1 character in body
Source Link
mikeazo
mikeazo
  • 2.8k
  • 17
  • 30

The problem with the method that you have suggested is that it is basically a partial-key exposure of RSA. You are exposing some bits of a factor of a semiprime. Dan Boneh's survey on RSA attacks lists a theorem from Coppersmith that states that if the n/4 least significant or most significant bits of a factor of N are known, then N can be factored efficiently. Since you want to leak way more than n/4, I think your method would be susceptible to that attack.

The good news is, Boneh gives some insight into something that might work:

It is interesting that discrete log-based cryptosystems, such as the ElGamal public key system, do not seem susceptible to partial key exposure. Indeed, if g^x mod p and a constant fraction of the bits of x are given, there is no known polynomial-time algorithm to compute the rest of x.

So, you could pick some random x, a large prime (1024 bits) p, and a generator g (in practice I'd use some standard NIST values for P and g). Compute g^x mod p, store that in your software. Store some number of bits of x in your program. The user must supply the remaining bits of x, all. Call their bits plus the stored bits x'. You compute g^x' mod p and see if that matches with what you had stored.

I believe that the statement from Boneh has not changed since it was published. That maybe something you want to ask on Crypto.SE, along with recommendations of how many bits should be left out of the source code.

The problem with the method that you have suggested is that it is basically a partial-key exposure of RSA. You are exposing some bits of a factor of a semiprime. Dan Boneh's survey on RSA attacks lists a theorem from Coppersmith that states that if the n/4 least significant or most significant bits of a factor of N are known, then N can be factored efficiently. Since you want to leak way more than n/4, I think your method would be susceptible to that attack.

The good news is, Boneh gives some insight into something that might work:

It is interesting that discrete log-based cryptosystems, such as the ElGamal public key system, do not seem susceptible to partial key exposure. Indeed, if g^x mod p and a constant fraction of the bits of x are given, there is no known polynomial-time algorithm to compute the rest of x.

So, you could pick some random x, a large prime (1024 bits) p, and a generator g (in practice I'd use some standard NIST values for P and g). Compute g^x mod p, store that in your software. Store some number of bits of x in your program. The user must supply the remaining bits of x, all their bits plus the stored bits x'. You compute g^x' mod p and see if that matches with what you had stored.

I believe that the statement from Boneh has not changed since it was published. That maybe something you want to ask on Crypto.SE, along with recommendations of how many bits should be left out of the source code.

The problem with the method that you have suggested is that it is basically a partial-key exposure of RSA. You are exposing some bits of a factor of a semiprime. Dan Boneh's survey on RSA attacks lists a theorem from Coppersmith that states that if the n/4 least significant or most significant bits of a factor of N are known, then N can be factored efficiently. Since you want to leak way more than n/4, I think your method would be susceptible to that attack.

The good news is, Boneh gives some insight into something that might work:

It is interesting that discrete log-based cryptosystems, such as the ElGamal public key system, do not seem susceptible to partial key exposure. Indeed, if g^x mod p and a constant fraction of the bits of x are given, there is no known polynomial-time algorithm to compute the rest of x.

So, you could pick some random x, a large prime (1024 bits) p, and a generator g (in practice I'd use some standard NIST values for P and g). Compute g^x mod p, store that in your software. Store some number of bits of x in your program. The user must supply the remaining bits of x. Call their bits plus the stored bits x'. You compute g^x' mod p and see if that matches with what you had stored.

I believe that the statement from Boneh has not changed since it was published. That maybe something you want to ask on Crypto.SE, along with recommendations of how many bits should be left out of the source code.

Source Link
mikeazo
mikeazo
  • 2.8k
  • 17
  • 30

The problem with the method that you have suggested is that it is basically a partial-key exposure of RSA. You are exposing some bits of a factor of a semiprime. Dan Boneh's survey on RSA attacks lists a theorem from Coppersmith that states that if the n/4 least significant or most significant bits of a factor of N are known, then N can be factored efficiently. Since you want to leak way more than n/4, I think your method would be susceptible to that attack.

The good news is, Boneh gives some insight into something that might work:

It is interesting that discrete log-based cryptosystems, such as the ElGamal public key system, do not seem susceptible to partial key exposure. Indeed, if g^x mod p and a constant fraction of the bits of x are given, there is no known polynomial-time algorithm to compute the rest of x.

So, you could pick some random x, a large prime (1024 bits) p, and a generator g (in practice I'd use some standard NIST values for P and g). Compute g^x mod p, store that in your software. Store some number of bits of x in your program. The user must supply the remaining bits of x, all their bits plus the stored bits x'. You compute g^x' mod p and see if that matches with what you had stored.

I believe that the statement from Boneh has not changed since it was published. That maybe something you want to ask on Crypto.SE, along with recommendations of how many bits should be left out of the source code.