Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How hard can generating 1024-bit primes be?

glitchcomet.com

Post reply on HN
Print view View original

81–89 of 89 posts

Re: How hard can generating 1024-bit primes be?

#81

Post by cratermoon »

dgacmu wrote: post #69
codeflo wrote: post #67

Earlier quoted context omitted.

Do you know why said cryptocurrency would use such a bespoke proof-of-work function? I.e., was it just someone ignorant who had only a vague idea that cryptography somehow uses prime numbers and didn’t know when or why, or was there a deeper reason?

There was a really popular trend among cryptocurrencies at some point of creating a new proof of work function as a way to differentiate your coin from the sea of Bitcoin clones. Coin creators would then make unsupported claims about why their new pow was better than Bitcoin (claims such as GPU, resistance, asic resistance, or some kind of social good were common). In the case of the prime number coins (primecoin, ri…

> New coins in particular depend on those miners acting as marketers to shill the coin

Isn't that the definition of a pyramid scheme?

Re: How hard can generating 1024-bit primes be?

#82

Post by adgjlsfhk1 »

cratermoon wrote: post #81
dgacmu wrote: post #69

Earlier quoted context omitted.

There was a really popular trend among cryptocurrencies at some point of creating a new proof of work function as a way to differentiate your coin from the sea of Bitcoin clones. Coin creators would then make unsupported claims about why their new pow was better than Bitcoin (claims such as GPU, resistance, asic resistance, or some kind of social good were common). In the case of the prime number coins (primecoin, ri…

> New coins in particular depend on those miners acting as marketers to shill the coin Isn't that the definition of a pyramid scheme?

welcome to cryptocurrency.

Re: How hard can generating 1024-bit primes be?

#83

Post by pclmulqdq »

SAI_Peregrinus wrote: post #74
pclmulqdq wrote: post #39

One quick thing to add to this: /dev/urandom does not generate "true" random numbers. TRNGs generate 1 bit out per bit of entropy they collect from the environment, while /dev/urandom will not stop generating random bits when it runs out of entropy. That makes it a CSPRNG that is seeded by a TRNG. For all practical purposes, a CSPRNG seeded by a TRNG is almost as good as a TRNG, but it isn't quite the same. Linux use…

A HWRNG is not necessarily a TRNG. As you say, a TRNG has one bit of entropy per bit of output. There's no way to prove this property is even possible in this physical universe, since it requires perfect unpredictability. Urandom is a CSPRNG seeded by a HWRNG.

This is true. The Intel HWRNG has actually been thought to be suspect in this regard in the past, although I don't think there's actual data about that.

Urandom also takes entropy from things like mouse movements, inter-onset intervals of key presses, and (on servers) hard drive seek times, so it actually does take in some of its own entropy in addition to that provided by the CPU.

Re: How hard can generating 1024-bit primes be?

#85

Post by jcalvinowens »

winternewt wrote: post #61
jcalvinowens wrote: post #52

Earlier quoted context omitted.

Of course. But that's ugly and hard to follow compared to the C implementation I linked (at least, in my opinion). And int128 support isn't ubiquitous.

Even so, if you wrap it in a function and make sure to document what's happening, I would argue that a version without asm() is preferable. It gives the compiler more leeway for optimization and is easier to read for someone who isn't well-versed in GCC's weird asm syntax. See the generated code for these two alternative implementations: https://godbolt.org/z/3vno6G46j

That's actually just a bug: the x86 asm constraints were needlessly forcing the compiler to use rdx as the input register for the multiply instruction.

With that fixed, it's the same: https://godbolt.org/z/M571P371K

But after staring at this for a little while, I realized simply reversing the order of the fields in the dword struct will make the result from the multiply instruction already match the way 128-bit structs are returned in registers under the x86_64 calling convention! This is quite a bit better: https://godbolt.org/z/MbfG63vej

Also worth noting the asm makes nicer code on arm64: https://godbolt.org/z/7eas6s9vK

https://github.com/jcalvinowens/toy-rsa/commit/59ef9ea905dbd... https://github.com/jcalvinowens/toy-rsa/commit/ceaa8a4dd0834...

Re: How hard can generating 1024-bit primes be?

#86

Post by jcalvinowens »

AndriyKunitsyn wrote: post #62
jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

Curiously, C actually has bignums. Now. In C23, they added a _BitInt(N) type (e.g., "_BitInt(1024)" for a 128-byte type). The compiler support for that is limited, though. To let N be >128 in Clang, -fexperimental-max-bitint-width=N flag can be provided. If N>128 and _BitInt(N) is divided by something, the compiler will just crash, but +, -, * all work as expected.

Neat. Maybe in ten years I'll actually be able rely on it existing in code I write!

Re: How hard can generating 1024-bit primes be?

#87

Post by winternewt »

jcalvinowens wrote: post #85
winternewt wrote: post #61

Earlier quoted context omitted.

Even so, if you wrap it in a function and make sure to document what's happening, I would argue that a version without asm() is preferable. It gives the compiler more leeway for optimization and is easier to read for someone who isn't well-versed in GCC's weird asm syntax. See the generated code for these two alternative implementations: https://godbolt.org/z/3vno6G46j

That's actually just a bug: the x86 asm constraints were needlessly forcing the compiler to use rdx as the input register for the multiply instruction. With that fixed, it's the same: https://godbolt.org/z/M571P371K But after staring at this for a little while, I realized simply reversing the order of the fields in the dword struct will make the result from the multiply instruction already match the way 128-bit struc…

Yes I also noticed the bug in the constraints and came to the same conclusion that changing them yields the same code for both implementations. But I figured that the fact that a function with a single asm instruction has a bug kind of supports my point. :)

As for the codegen on ARM, I don't think your asm implementation is correct there either. As far as I can tell the UMULL instruction only cares about the least significant 32 bits in the source registers, regardless if you're on a 64-bit CPU: https://developer.arm.com/documentation/ddi0602/2024-03/Base...

Re: How hard can generating 1024-bit primes be?

#88

Post by jcalvinowens »

winternewt wrote: post #87
jcalvinowens wrote: post #85

Earlier quoted context omitted.

That's actually just a bug: the x86 asm constraints were needlessly forcing the compiler to use rdx as the input register for the multiply instruction. With that fixed, it's the same: https://godbolt.org/z/M571P371K But after staring at this for a little while, I realized simply reversing the order of the fields in the dword struct will make the result from the multiply instruction already match the way 128-bit struc…

Yes I also noticed the bug in the constraints and came to the same conclusion that changing them yields the same code for both implementations. But I figured that the fact that a function with a single asm instruction has a bug kind of supports my point. :) As for the codegen on ARM, I don't think your asm implementation is correct there either. As far as I can tell the UMULL instruction only cares about the least si…

Very much disagree with your point about constraints. A bug existing in 10+ year old code that has never really been tested and run by four people doesn't support any point. In real life one actually checks these things, it's not that complex :)

Case in point: counting the f's in your constants took me longer than finding that constraint bug did. You would argue ULLONG_MAX would fix that, I suppose.

You're right, that's the 32-bit arm instruction, doh. In my defense, this code was written before 64-bit ARM existed!

Re: How hard can generating 1024-bit primes be?

#89

Post by sliken »

sva_ wrote: post #10
throw0101b wrote: post #3

I remember first trying out PGP in the early 1990s on a 80386 or 80486 on Linux and it took forever to generate a new key.

If you try to generate a PGP key using GPG on a fresh Linux system, it may flatout refuse to do so claiming there is not sufficient entropy. Or at least it was like that some years ago.

As a result they added a "type into this buffer" to add entropy, which used what you typed and the timing of the keystrokes to help. Similarly graphical UIs say "draw in this region" for similar boost to randomness that helps avoid lack of entropy problems.
Post reply on HN