0
$\begingroup$

I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 bit RSA keys, but Wikipedia doesn't say how long it would take in modern CPUs.

-- Background --

I am designing a virtual roulette game where the ball is spun (the number is chosen) before the player bets. As a proof of that but I show the player the product of two primes, one of them is used as the random number seed.

I would like to know what is the minimum suitable size for this number such as the cost of factoring it will be greater than the maximum prize I offer.

$\endgroup$
4
$\begingroup$

Instead of reinventing the wheel, I recommend that you use the cryptographic concept of a commitment scheme. Pick your needed randomness as you normally would, commit to it, and then reveal your committed randomness after betting.

$\endgroup$
  • $\begingroup$ I suppose the OP needs a commitment scheme which can be verified (and understood) manually by a layman. $\endgroup$ – M. Alaggan Jun 6 '11 at 20:51
  • $\begingroup$ Couldn't understand it the first time. I'll try later $\endgroup$ – Jader Dias Jun 6 '11 at 23:35
  • $\begingroup$ I got it. A hash function will do the job. Someone is already using it for the same purpose I devised bitcoin-kamikaze.com $\endgroup$ – Jader Dias Jun 7 '11 at 0:29
6
$\begingroup$

To turn the question around, one could equivalently ask: "How large must my prime be in order to be secure until year X against the resource plausibly available to a potent (e.g. government-funded) attacker?" This question is being regularly reassessed in various studies yielding recommended key lengths for crypto systems. A regularly updated web page summarizing these reports can be found here.

$\endgroup$

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.