Time for calculations!
hoho, love it
==================
can you explain in short why the size of RAM matters in this algorithm?
The essence of the BSGS (baby-step-gigant-step) algorithm in simple words.
1)We calc 1st pubkey table and save in RAM.
2)We calc 2st pubkey table and on the fly compare it with 1st table in ram without save.
3)If a match is found, the privkey is ready.
The size of the tables is the same and less than the square root of the bit size of the key being flushed.
The comparison procedure in RAM is essentially the multiplication of two square roots, example 2^40 * 2^40 = 2^80.
2^80 is very difficult to calculate, but 2^40 times easier. Ok?
RAM is necessary because the comparison should be as FAST as possible.
Computational complexity
When there is enough RAM, each puzzle requires x2 more calculations.
But in case of a lack of ram, each puzzle the computational complexity increases x4 (exponential growth).
If there is not enough ram, you can compare BSvsGS by calculating BS/GS in chunks.
But the price is high - an exponential increase in computing.
For comparison with the next piece of BS loaded into memory, we are forced to re-calculate the GS completely.
An illustrative example showing dimensions.
Increase computation that you have 16Gb free RAM (penalties if not enough)
#61,#62 16Gb/16=1 x1
[BS]
[GS]
.......................................
#63,#64 32Gb/16=2 x3 ((2*2+2)/2)
[BS][BS]
[GS][GS][GS][GS]
.......................................
#65,#66 64Gb/16=4 x10 ((4*4+4)/2)
[BS][BS]
[BS][BS]
[GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS]
.......................................
#67,#68 128Gb/16=8 x36 ((8*8+8)/2)
[BS][BS][BS][BS]
[BS][BS][BS][BS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
.......................................
#69,#70 256Gb/16=16 x136 ((16*16+16)/2)
[BS][BS][BS][BS]
[BS][BS][BS][BS]
[BS][BS][BS][BS]
[BS][BS][BS][BS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
[GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS][GS]
norm if enough ram
x1->x2->x4->x8->x16
penalties if not enough ram
x1->x3->x10->x36->x136
Due to this fact, the GPU calculations will be much less efficient.
The width of the memory bus is crucial, as the most powerful data exchange (Vega/Volta) is assumed.
==================
How long did it take and how much mem does it require ...
I realize how long it will last and how much RAM will need.
what equipment is needed to solve the puzzle and what software?
Calculate the time to restore the keys of the puzzle.
The use of the program break_short(brsh) is supposed
1core brsh = 0,27 Mkeys/s
128cr brsh = 34,5 Mkeys/s
Time is indicated for calculation only for one table(BS/GS), but they should be considered two, that is, double the actual time.
Ideal calculations suggest that you have enough RAM (no penalties)
2^x |#puzzle| memory | 1core brsh | 128cr brsh |
------------------------------------------------
2^23(#47,#48) 128(Mb) 30(sec) | 0() |
2^24(#49,#50) 256(Mb) 60(sec) | 0,5(sec)|
2^25(#51,#52) 512(Gb) 2(min) | 1(sec)|
2^26(#53,#54) 1(Gb) 4(min) | 2(sec)|
2^27(#55,#56) 2(Gb) 8(min) | 4(sec)|
2^28(#57,#58) 4(Gb) 16(min) | 8(sec)|
2^29(#59,#60) 8(Gb) 32(min) | 16(sec)|
2^30(#61,#62) 16(Gb) 1(h) | 32(sec)|
2^31(#63,#64) 32(Gb) 2(h) | 1(min)|
2^32(#65,#66) 64(Gb) 4(h) | 2(min)|
-----double-ram-x2(Gb)-because-need-x32->x64----
2^33(#67,#68) 256(Gb) 8(h) | 4(min)|
2^34(#69,#70) 512(Gb) 16(h) | 8(min)|
2^35(#71,#72) 1(Tb) 32(h) | 16(min)|
2^36(#73,#74) 2(Tb) 2,5(d) | 32(min)|
2^37(#75,#76) 4(Tb) 5(d) | 1(h) |
2^38(#77,#78) 8(Tb) 10(d) | 2(h) |
2^39(#79,#80) 16(Tb) 20(d) | 4(h) |
2^40(#81,#82) 32(Tb) 40(d) | 8(h) |
2^41(#83,#84) 64(Tb) 3(m) | 16(h) |
2^42(#85,#86) 128(Tb) 6(m) | 32(h) |
2^43(#87,#88) 256(Tb) 9(m) | 2,5(d) |
2^44(#89,#90) 512(Tb) 1,5(y) | 5(d) |
2^45(#91,#92 1(Pb) 3(y) | 10(d) |
2^46(#93,#94) 2(Pb) 6(y) | 20(d) |
2^47(#95,#96) 4(Pb) 12(y) | 40(d) |
2^47(#97,#98) 8(Pb) 24(y) | 3(m) |
2^47(#99,#100) 16(Pb) 48(y) | 6(m) |
* On Linux operating systems, performance is 25% higher than on Windows.
* Assumes server instance AmazonAWS 4Tb ddr4 128cores (x1e.32xlarge)
* The actual performance of 128 cores can be reduced to 96 cores if the server has 64 real cores of 2 logical cores each.
==================
Calculations suggest that you have 4Tb of memory (penalties if not enough)
2^x |#puzzle | memory | norm/penalty| 1core brsh | 128cr brsh |
----------------------------------------------------------------
2^37(#75,#76) 4(Tb)| 1/ 1| 5(d)/ 5(d)| 1(h)/ 1(h)|
2^38(#77,#78) 8(Tb)| 2/ 3| 10(d)/ 15(d)| 2(h)/ 3(h)|
----------------------------------------------------------------
2^39(#79,#80) 16(Tb)| 4/ 10| 20(d)/1,5(m)| 4(h)/ 10(h)|
2^40(#81,#82) 32(Tb)| 8/ 36| 40(d)/ 6(m)| 8(h)/ 36(h)|
2^41(#83,#84) 64(Tb)| 16/ 136| 3(m)/ 2(y)| 16(h)/ 6(d)|
----------------------------------------------------------------
2^42(#85,#86) 128(Tb)| 32/ 528| 6(m)/ 8(y)| 32(h)/ 22(d)|
2^43(#87,#88) 256(Tb)| 64/ 2080| 9(m)/ 24(y)|2,5(d)/ 3(m)|
----------------------------------------------------------------
2^44(#89,#90) 512(Tb)| 128/ 8256|1,5(y)/ 95(y)| 5(d)/ 10(m)|
2^45(#91,#92) 1(Pb)| 256/ 32896| 3(y)/385(y)| 10(d)/3,5(y)|
2^46(#93,#94) 2(Pb)| 512/ 131328| 6(y)/ ?(y)| 20(d)/ 14(y)|
----------------------------------------------------------------
2^47(#95,#96) 4(Pb)|1024/ 524800| 12(y)/ ?(y)| 40(d)/ 56(y)|
2^47(#97,#98) 8(Pb)|2048/2098176| 24(y)/ ?(y)| 3(m)/252(y)|
----------------------------------------------------------------
2^47(#99,#100) 16(Pb)|4096/8390656| 48(y)/ ?(y)| 6(m)/ ?(y)|
* penalty calculation formula
penalty = (((norm * norm) + norm) 2)
How is this possible?
Now restore the chronology of events
May 31, the Author deliberately discloses the pubkeys in every fifth transaction in order to update and improve the puzzle.
On June 7, a vigilant certain Mr.X gets #65, then #70, #75, #80 within 4 days.
By the above calculation it is easy to understand how he did it.
He modified break_short, adding 64-128bit, multi-core and the ability to calculate BS in chunks.
(even a novice C programmer can easily add these modifications to the program)
Then he rented amazonaws x1e.32xlarge with 2-4Tb for 4 days (250$/day), spending 1k $ and earned 20k $
I hate you, but you're well done)
How is it going in London?
You know, Bivonas is not the best place)
Why didn't he find #85? As can be seen from the table it is unprofitable! (without significant improvement of Software or Server)
Arulbero has already wrote some posts of improving the Software, let's leave it.
I think that beyond #85 it will be very difficult to recover the private key, even with 1 TB of RAM (with the Baby-Giant Step algorithm).
Nvme ssd as a swap?
SSD is much slower than RAM. (DDR4 47GB/s)
Let's talk about Servers.
We are not so important processor or videocard. But the size of RAM is very important to us.
The problem is that more than 4Tb RAM is not mass produced.
Consider a few ideas around this.
NVMe has approximately the same bandwidth as DDR4 RAM, but the access speed is much lower.
A HDD has a response time of about 10ms, an SSD will respond in 0.1ms, an Optain will respond in 8micros, a RAM will respond in 50ns.
0.1ms is equal to 100,000 ns.
This means that RAM can serve data in memory 1000 times faster than NVMe disk.
I checked the paging file(swap) on M.2 RAID0 NVMe - it's useless. its slooooooooow (100Kkey/s)
But there is news from Western Digital
Memory Extension Drive
Ultrastar DC ME200 1,2,4Tb
https://blog.westerndigital.com/how-ultrastar-memory-extension-drive-works/https://www.westerndigital.com/products/data-center-drives/ultrastar-dc-me200-memory-extension-driveAccording to WD, if we take the appeal to 786 GB of DRAM for pure performance, which is estimated at 1,080 million transactions per second, then a 3: 1 mix (576 GB of Ultrastar and 192 GB of DRAM) will drop to 91% of performance or to 983 thousand transactions, and at a ratio of 7: 1 (672 GB Ultrastar and 96 GB DRAM), the performance will decrease to 85% or 918 thousand transactions per second.
Intel Optain(Optane)
Optain looks like an acceleration cache for hard drives.
It can also work in the expansion mode of RAM (!).
It will be useful for a large number of small file accesses(!).
Optain has less capacity than SSD.
A 7th generation Intel processor is required, so it does not improve performance for older PCs.
Optane can to 7 microseconds at readings.
Optane can only get QD1 performance. This is impressive (5 times faster than current generation SSM NVMe).
Intel Optane SSD 750Gb
https://itpeernetwork.intel.com/optane-intel-memory-drive-technology/Optane DC Persistent Memory DIMM format
https://lenovopress.com/lp1066-intel-optane-dc-persistent-memoryYou are the only one that has the working code for that
Not one) #70 success calc.
0290E6900A58D33393BC1097B5AED31F2E4E7CBD3E5466AF958665BC0121248483
00000000000000000000000000000000000000000000003*9*4*6*3*A*C*E*1
Our legendary master, why so long, maybe it's time to clean up the Xeon registers?)
