Hackovanie suchalovho kluca

Scholtz · October 20, 2017, 11:14am

Zadanie: Nájsť suchalov D (privátny kľúč).

Existujú 2 cesty:

P*Q = N
… ak sa zistí P a Q, tak sa dá z E vypočítať D
iterácia ktorá nájde rovno D
Research paper:
https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf

Konštanty:
N = 19320234965388231365540331093872230283778945634556596682214163280186385949444714747846212850116256215110019915157460836374458213753399271651569995871137126916385002459283305264844322656670858555695350602088849590984911208795341527784373572568199485660335040039545712139902834483955502131356223511756716987839814223560695397544760324236593252526008468733300092541502234485830371545572743645953216843356025562571409688147979531382601119854626778211029567854618943714104772640084682336503263097825328909488844956732298839600439486781366754445139880815199642118131001675897147726276626348623513074701194667574356320780611
E = 65537

N mod 3 === 1 (podla research paperu toto je zle)
N mod 4 === 3

N ^ (1/2) = O = 138997248049694247770541517600378173283217214543602676445502427174391582170733502029426880009511527474814359326704988215079793018217022234099038216552755211207779848720241586803576921092459037601125335313048606503498497510086189254695312463105962720647280557925658285588366218328455179220807665234241785776873

Prvý bajt O: 11000101

P < O < Q
Podľa research paperu, by malo byť
P min = 11000000
P max = 11001111

Q min = 11000000
Q max = 11001111

Sedi…

MinP = 67413492557336846539848944654588427510674136710336496477536280434149753427062861174765678995902826007920042704951772509122046163305406233434817786489802796641662960034324556978613332350467285294794906107031877163314306505878423580552717416452810213936256441506719861839980217226929893614313258623609084051456

O - MinP = 71583755492357401230692572945789745772543077833266179967966146740241828743670640854661201013608701466894316621753215705957746854911616000664220430062952414566116888685917029824963588741991752306330429206016729340184191004207765674142595046653152506711024116418938423748386001101525285606494406610632701725417

Moj noteboook mi dava N.mod(iter) == 0 test 5300x za sekundu na single threade

To vyzera ze by som ho mohol nechat pracovat 73608373250062070383308159345069474483178433689658124211146357916393423990066890695717242090215349851415140968893881583160864521428859007506570783641032054334450297032587086148905193429493454418670189232870236245757235440555581303014410176944455596977918022260132623427651355287965030588654414115575 dni a potom by som mal zaruceny vysledok… niekto nejake navrhy na vylepsenie?

mohol by otestovat niekto mod rychlost na cuda ?

jsuchal · October 20, 2017, 11:29am

Pre úplnosť dodávam, že môj certifikát bol včera úspešne revoknutý a dávam súhlas na faktorizáciu tohto číselka resp. získanie privátnej časti.

Pre konšpirátorov: K privátnemu klúču sa nedá nijako dostať (je zapečený v hw prostriedku), teda nemám k nemu prístup ani ja s BOKom, ZEPom ani ničím. Čiže úvahy o tom, ako toto je dohodnutá akcia sú mimo.

Scholtz · October 20, 2017, 2:15pm

Mozno by sme sa mali dat smerom, ze N%3=1 a N%4=3

tu su prve cisla tejto postupnosti rozlozene podla 4t + 3

1 * 4+3=7
4 * 4+3=19
7 * 4+3=31
10 * 4+3=43
13 * 4+3=55
16 * 4+3=67
19 * 4+3=79
22 * 4+3=91
25 * 4+3=103
28 * 4+3=115
31 * 4+3=127
34 * 4+3=139
37 * 4+3=151
40 * 4+3=163
43 * 4+3=175
46 * 4+3=187
49 * 4+3=199
52 * 4+3=211
55 * 4+3=223
58 * 4+3=235
61 * 4+3=247
64 * 4+3=259
67 * 4+3=271
70 * 4+3=283
73 * 4+3=295
76 * 4+3=307
79 * 4+3=319
82 * 4+3=331
85 * 4+3=343
88 * 4+3=355
91 * 4+3=367
94 * 4+3=379
97 * 4+3=391
100 * 4+3=403
103 * 4+3=415
106 * 4+3=427
109 * 4+3=439
112 * 4+3=451
115 * 4+3=463
118 * 4+3=475
121 * 4+3=487
124 * 4+3=499
127 * 4+3=511
130 * 4+3=523
133 * 4+3=535
136 * 4+3=547
139 * 4+3=559
142 * 4+3=571
145 * 4+3=583
148 * 4+3=595
151 * 4+3=607
154 * 4+3=619
157 * 4+3=631
160 * 4+3=643
163 * 4+3=655
166 * 4+3=667
169 * 4+3=679
172 * 4+3=691
175 * 4+3=703
178 * 4+3=715
181 * 4+3=727
184 * 4+3=739
187 * 4+3=751
190 * 4+3=763
193 * 4+3=775
196 * 4+3=787
199 * 4+3=799
202 * 4+3=811
205 * 4+3=823
208 * 4+3=835
211 * 4+3=847
214 * 4+3=859
217 * 4+3=871
220 * 4+3=883
223 * 4+3=895
226 * 4+3=907
229 * 4+3=919
232 * 4+3=931
235 * 4+3=943
238 * 4+3=955
241 * 4+3=967
244 * 4+3=979
247 * 4+3=991

Scholtz · October 20, 2017, 2:28pm

Tak mimochodom

N%3 = 1
N%4 = 3
N%5 = 1
N%6 = 1
N%7 = 1
N%8 = 3
N%9 = 1
N%10 = 1
N%11 = 1
N%12 = 7
N%13 = 1
N%14 = 1
N%15 = 1
N%16 = 3
N%17 = 1
N%18 = 1
N%19 = 11
N%20 = 11
N%21 = 1
N%22 = 1
N%23 = 16
N%24 = 19
N%25 = 11
N%26 = 1
N%27 = 10
N%28 = 15
N%29 = 1
N%30 = 1
N%31 = 4
N%32 = 3
N%33 = 1
N%34 = 1
N%35 = 1
N%36 = 19
N%37 = 1
N%38 = 11
N%39 = 1
N%40 = 11
N%41 = 37
N%42 = 1
N%43 = 1
N%44 = 23
N%45 = 1
N%46 = 39
N%47 = 36
N%48 = 19
N%49 = 36
N%50 = 11
N%51 = 1
N%52 = 27
N%53 = 24
N%54 = 37
N%55 = 1
N%56 = 43
N%57 = 49
N%58 = 1
N%59 = 17
N%60 = 31
N%61 = 58
N%62 = 35
N%63 = 1
N%64 = 3
N%65 = 1
N%66 = 1
N%67 = 40
N%68 = 35
N%69 = 16
N%70 = 1
N%71 = 25
N%72 = 19
N%73 = 1
N%74 = 1
N%75 = 61
N%76 = 11
N%77 = 1
N%78 = 1
N%79 = 46
N%80 = 51
N%81 = 10
N%82 = 37
N%83 = 30
N%84 = 43
N%85 = 1
N%86 = 1
N%87 = 1
N%88 = 67
N%89 = 32
N%90 = 1
N%91 = 1
N%92 = 39
N%93 = 4
N%94 = 83
N%95 = 11
N%96 = 67
N%97 = 1
N%98 = 85
N%99 = 1
N%100 = 11
N%101 = 80
N%102 = 1
N%103 = 79
N%104 = 27
N%105 = 1
N%106 = 77
N%107 = 4
N%108 = 91
N%109 = 75
N%110 = 1
N%111 = 1
N%112 = 99
N%113 = 1
N%114 = 49
N%115 = 16
N%116 = 59
N%117 = 1
N%118 = 17
N%119 = 1
N%120 = 91
N%121 = 67
N%122 = 119
N%123 = 37
N%124 = 35
N%125 = 111
N%126 = 1
N%127 = 1
N%128 = 67
N%129 = 1
N%130 = 1
N%131 = 81
N%132 = 67
N%133 = 106
N%134 = 107
N%135 = 91
N%136 = 35
N%137 = 38
N%138 = 85
N%139 = 6
N%140 = 71
N%141 = 130
N%142 = 25
N%143 = 1
N%144 = 19
N%145 = 1
N%146 = 1
N%147 = 85
N%148 = 75
N%149 = 104
N%150 = 61
N%151 = 91
N%152 = 11
N%153 = 1
N%154 = 1
N%155 = 66
N%156 = 79
N%157 = 99
N%158 = 125
N%159 = 130
N%160 = 131
N%161 = 85
N%162 = 91
N%163 = 25
N%164 = 119
N%165 = 1
N%166 = 113
N%167 = 56
N%168 = 43
N%169 = 92
N%170 = 1
N%171 = 163
N%172 = 87
N%173 = 16
N%174 = 1
N%175 = 36
N%176 = 67
N%177 = 76
N%178 = 121
N%179 = 52
N%180 = 91
N%181 = 5
N%182 = 1
N%183 = 58
N%184 = 131
N%185 = 1
N%186 = 97
N%187 = 1
N%188 = 83
N%189 = 64
N%190 = 11
N%191 = 51
N%192 = 67
N%193 = 192
N%194 = 1
N%195 = 1
N%196 = 183
N%197 = 178
N%198 = 1
N%199 = 111
N%200 = 11
N%201 = 40
N%202 = 181
N%203 = 1
N%204 = 103
N%205 = 201
N%206 = 79
N%207 = 154
N%208 = 131
N%209 = 144
N%210 = 1
N%211 = 107
N%212 = 183
N%213 = 25
N%214 = 111
N%215 = 1
N%216 = 91
N%217 = 190
N%218 = 75
N%219 = 1
N%220 = 111
N%221 = 1
N%222 = 1
N%223 = 60
N%224 = 99
N%225 = 136
N%226 = 1
N%227 = 57
N%228 = 163
N%229 = 61
N%230 = 131
N%231 = 1
N%232 = 59
N%233 = 19
N%234 = 1
N%235 = 36
N%236 = 135
N%237 = 46
N%238 = 1
N%239 = 51
N%240 = 211
N%241 = 1
N%242 = 67
N%243 = 172
N%244 = 119
N%245 = 36
N%246 = 37
N%247 = 144
N%248 = 35
N%249 = 196
N%250 = 111
N%251 = 124
N%252 = 127
N%253 = 177
N%254 = 1
N%255 = 1
N%256 = 67
N%257 = 1
N%258 = 1
N%259 = 1
N%260 = 131
N%261 = 1
N%262 = 81
N%263 = 184
N%264 = 67
N%265 = 236
N%266 = 239
N%267 = 121
N%268 = 107
N%269 = 205
N%270 = 91
N%271 = 39
N%272 = 35
N%273 = 1
N%274 = 175
N%275 = 111
N%276 = 223
N%277 = 213
N%278 = 145
N%279 = 190
N%280 = 211
N%281 = 90
N%282 = 271
N%283 = 181
N%284 = 167
N%285 = 106
N%286 = 1
N%287 = 78
N%288 = 163
N%289 = 137
N%290 = 1
N%291 = 1
N%292 = 147
N%293 = 149
N%294 = 85
N%295 = 76
N%296 = 75
N%297 = 199
N%298 = 253
N%299 = 131
N%300 = 211
N%301 = 1
N%302 = 91
N%303 = 181
N%304 = 163
N%305 = 241
N%306 = 1
N%307 = 275
N%308 = 155
N%309 = 79
N%310 = 221
N%311 = 278
N%312 = 235
N%313 = 44
N%314 = 99
N%315 = 1
N%316 = 283
N%317 = 234
N%318 = 289
N%319 = 1
N%320 = 131
N%321 = 4
N%322 = 85
N%323 = 239
N%324 = 91
N%325 = 261
N%326 = 25
N%327 = 184
N%328 = 283
N%329 = 36
N%330 = 1
N%331 = 1
N%332 = 279
N%333 = 1
N%334 = 223
N%335 = 241
N%336 = 211
N%337 = 1
N%338 = 261
N%339 = 1
N%340 = 171
N%341 = 221
N%342 = 163
N%343 = 330
N%344 = 259
N%345 = 16
N%346 = 189
N%347 = 109
N%348 = 175
N%349 = 66
N%350 = 211
N%351 = 118
N%352 = 67
N%353 = 58
N%354 = 253
N%355 = 96
N%356 = 299
N%357 = 1
N%358 = 231
N%359 = 144
N%360 = 91
N%361 = 258
N%362 = 5
N%363 = 67
N%364 = 183
N%365 = 1
N%366 = 241
N%367 = 258
N%368 = 131
N%369 = 37
N%370 = 1
N%371 = 183
N%372 = 283
N%373 = 49
N%374 = 1
N%375 = 361
N%376 = 83
N%377 = 1
N%378 = 253
N%379 = 327
N%380 = 11
N%381 = 1
N%382 = 51
N%383 = 112
N%384 = 67
N%385 = 1
N%386 = 385
N%387 = 1
N%388 = 195
N%389 = 361
N%390 = 1
N%391 = 154
N%392 = 379
N%393 = 343
N%394 = 375
N%395 = 46
N%396 = 199
N%397 = 333
N%398 = 111
N%399 = 106
N%400 = 211
N%401 = 173
N%402 = 241
N%403 = 66
N%404 = 383
N%405 = 91
N%406 = 1
N%407 = 1
N%408 = 307
N%409 = 5
N%410 = 201
N%411 = 175
N%412 = 79
N%413 = 253
N%414 = 361
N%415 = 196
N%416 = 131
N%417 = 145
N%418 = 353
N%419 = 289
N%420 = 211
N%421 = 279
N%422 = 107
N%423 = 271
N%424 = 395
N%425 = 86
N%426 = 25
N%427 = 302
N%428 = 111
N%429 = 1
N%430 = 1
N%431 = 320
N%432 = 307
N%433 = 198
N%434 = 407
N%435 = 1
N%436 = 75
N%437 = 315
N%438 = 1
N%439 = 36
N%440 = 331
N%441 = 379
N%442 = 1
N%443 = 27
N%444 = 223
N%445 = 121
N%446 = 283
N%447 = 253
N%448 = 323
N%449 = 67
N%450 = 361
N%451 = 78
N%452 = 227
N%453 = 91
N%454 = 57
N%455 = 1
N%456 = 163
N%457 = 54
N%458 = 61
N%459 = 307
N%460 = 131
N%461 = 114
N%462 = 1
N%463 = 247
N%464 = 291
N%465 = 376
N%466 = 19
N%467 = 438
N%468 = 235
N%469 = 442
N%470 = 271
N%471 = 256
N%472 = 371
N%473 = 1
N%474 = 283
N%475 = 11
N%476 = 239
N%477 = 289
N%478 = 51
N%479 = 438
N%480 = 451
N%481 = 1
N%482 = 1
N%483 = 85
N%484 = 67
N%485 = 1
N%486 = 415
N%487 = 19
N%488 = 363
N%489 = 25
N%490 = 281
N%491 = 101
N%492 = 283
N%493 = 1
N%494 = 391
N%495 = 1
N%496 = 35
N%497 = 309
N%498 = 445
N%499 = 64
N%500 = 111
N%501 = 223
N%502 = 375
N%503 = 458
N%504 = 379
N%505 = 181
N%506 = 177
N%507 = 430
N%508 = 255
N%509 = 329
N%510 = 1
N%511 = 1
N%512 = 323
N%513 = 334
N%514 = 1
N%515 = 491
N%516 = 259
N%517 = 177
N%518 = 1
N%519 = 16
N%520 = 131
N%521 = 123
N%522 = 1
N%523 = 60
N%524 = 343
N%525 = 211
N%526 = 447
N%527 = 35
N%528 = 67
N%529 = 39
N%530 = 501
N%531 = 253
N%532 = 239
N%533 = 365
N%534 = 121
N%535 = 111
N%536 = 107
N%537 = 52
N%538 = 205
N%539 = 232
N%540 = 91
N%541 = 15
N%542 = 39
N%543 = 367
N%544 = 35
N%545 = 511
N%546 = 1
N%547 = 46
N%548 = 175
N%549 = 424
N%550 = 111
N%551 = 30
N%552 = 499
N%553 = 204
N%554 = 213
N%555 = 1
N%556 = 423
N%557 = 67
N%558 = 469
N%559 = 1
N%560 = 211
N%561 = 1
N%562 = 371
N%563 = 304
N%564 = 271
N%565 = 1
N%566 = 181
N%567 = 253
N%568 = 451
N%569 = 327
N%570 = 391
N%571 = 214
N%572 = 287
N%573 = 433
N%574 = 365
N%575 = 361
N%576 = 451
N%577 = 553
N%578 = 137
N%579 = 385
N%580 = 291
N%581 = 113
N%582 = 1
N%583 = 342
N%584 = 147
N%585 = 1
N%586 = 149
N%587 = 229
N%588 = 379
N%589 = 562
N%590 = 371
N%591 = 178
N%592 = 371
N%593 = 60
N%594 = 199
N%595 = 1
N%596 = 551
N%597 = 310
N%598 = 131
N%599 = 144
N%600 = 211
N%601 = 423
N%602 = 1
N%603 = 442
N%604 = 91
N%605 = 551
N%606 = 181
N%607 = 339
N%608 = 163
N%609 = 1
N%610 = 241
N%611 = 365
N%612 = 307
N%613 = 90
N%614 = 275
N%615 = 406
N%616 = 155
N%617 = 392
N%618 = 79
N%619 = 382
N%620 = 531
N%621 = 361
N%622 = 589
N%623 = 477
N%624 = 547
N%625 = 611
N%626 = 357
N%627 = 562
N%628 = 99
N%629 = 1
N%630 = 1
N%631 = 344
N%632 = 283
N%633 = 529
N%634 = 551
N%635 = 1
N%636 = 607
N%637 = 183
N%638 = 1
N%639 = 451
N%640 = 451
N%641 = 385
N%642 = 325
N%643 = 81
N%644 = 407
N%645 = 1
N%646 = 239
N%647 = 168
N%648 = 91
N%649 = 430
N%650 = 261
N%651 = 190
N%652 = 351
N%653 = 496
N%654 = 511
N%655 = 81
N%656 = 611
N%657 = 1
N%658 = 365
N%659 = 606
N%660 = 331
N%661 = 493
N%662 = 1
N%663 = 1
N%664 = 611
N%665 = 106
N%666 = 1
N%667 = 407
N%668 = 223
N%669 = 283
N%670 = 241
N%671 = 485
N%672 = 547
N%673 = 1
N%674 = 1
N%675 = 361
N%676 = 599
N%677 = 71
N%678 = 1
N%679 = 1
N%680 = 171
N%681 = 511
N%682 = 221
N%683 = 290
N%684 = 163
N%685 = 586
N%686 = 673
N%687 = 61
N%688 = 259
N%689 = 183
N%690 = 361
N%691 = 310
N%692 = 535
N%693 = 1
N%694 = 109
N%695 = 6
N%696 = 523
N%697 = 324
N%698 = 415
N%699 = 19
N%700 = 211
N%701 = 521
N%702 = 469
N%703 = 334
N%704 = 67
N%705 = 271
N%706 = 411
N%707 = 484
N%708 = 607
N%709 = 693
N%710 = 451
N%711 = 46
N%712 = 299
N%713 = 407
N%714 = 1
N%715 = 1
N%716 = 231
N%717 = 529
N%718 = 503
N%719 = 176
N%720 = 451
N%721 = 491
N%722 = 619
N%723 = 1
N%724 = 367
N%725 = 436
N%726 = 67
N%727 = 450
N%728 = 547
N%729 = 415
N%730 = 1
N%731 = 1
N%732 = 607
N%733 = 375
N%734 = 625
N%735 = 526
N%736 = 131
N%737 = 375
N%738 = 37
N%739 = 373
N%740 = 371
N%741 = 391
N%742 = 183
N%743 = 474
N%744 = 283
N%745 = 551
N%746 = 49
N%747 = 694
N%748 = 375
N%749 = 218
N%750 = 361
N%751 = 717
N%752 = 83
N%753 = 124
N%754 = 1
N%755 = 91
N%756 = 631
N%757 = 176
N%758 = 327
N%759 = 430
N%760 = 11
N%761 = 395
N%762 = 1
N%763 = 729
N%764 = 51
N%765 = 1
N%766 = 495
N%767 = 430
N%768 = 67
N%769 = 569
N%770 = 1
N%771 = 1
N%772 = 771
N%773 = 636
N%774 = 1
N%775 = 686
N%776 = 195
N%777 = 1
N%778 = 361
N%779 = 201
N%780 = 391
N%781 = 309
N%782 = 545
N%783 = 523
N%784 = 771
N%785 = 256
N%786 = 343
N%787 = 589
N%788 = 375
N%789 = 184
N%790 = 441
N%791 = 1
N%792 = 595
N%793 = 729
N%794 = 333
N%795 = 766
N%796 = 111
N%797 = 52
N%798 = 505
N%799 = 647
N%800 = 611
N%801 = 388
N%802 = 173
N%803 = 1
N%804 = 643
N%805 = 246
N%806 = 469
N%807 = 205
N%808 = 787
N%809 = 677
N%810 = 91
N%811 = 780
N%812 = 407
N%813 = 310
N%814 = 1
N%815 = 351
N%816 = 307
N%817 = 87
N%818 = 5
N%819 = 1
N%820 = 611
N%821 = 597
N%822 = 175
N%823 = 50
N%824 = 491
N%825 = 661
N%826 = 253
N%827 = 648
N%828 = 775
N%829 = 740
N%830 = 611
N%831 = 490
N%832 = 131
N%833 = 477
N%834 = 145
N%835 = 56
N%836 = 771
N%837 = 469
N%838 = 289
N%839 = 294
N%840 = 211
N%841 = 233
N%842 = 279
N%843 = 652
N%844 = 107
N%845 = 261
N%846 = 271
N%847 = 309
N%848 = 819
N%849 = 181
N%850 = 511
N%851 = 223
N%852 = 451
N%853 = 299
N%854 = 729
N%855 = 676
N%856 = 539
N%857 = 312
N%858 = 1
N%859 = 556
N%860 = 431
N%861 = 652
N%862 = 751
N%863 = 476
N%864 = 739
N%865 = 16
N%866 = 631
N%867 = 715
N%868 = 407
N%869 = 441
N%870 = 1
N%871 = 40
N%872 = 75
N%873 = 1
N%874 = 315
N%875 = 736
N%876 = 439
N%877 = 401
N%878 = 475
N%879 = 442
N%880 = 771
N%881 = 197
N%882 = 379
N%883 = 536
N%884 = 443
N%885 = 76
N%886 = 27
N%887 = 806
N%888 = 667
N%889 = 1
N%890 = 121
N%891 = 496
N%892 = 283
N%893 = 600
N%894 = 253
N%895 = 231
N%896 = 323
N%897 = 430
N%898 = 67
N%899 = 407
N%900 = 811
N%901 = 766
N%902 = 529
N%903 = 1
N%904 = 227
N%905 = 186
N%906 = 91
N%907 = 355
N%908 = 511
N%909 = 181
N%910 = 1
N%911 = 142
N%912 = 163
N%913 = 694
N%914 = 511
N%915 = 241
N%916 = 519
N%917 = 736
N%918 = 307
N%919 = 888
N%920 = 131
N%921 = 889
N%922 = 575
N%923 = 664
N%924 = 463
N%925 = 186
N%926 = 247
N%927 = 388
N%928 = 291
N%929 = 482
N%930 = 841
N%931 = 771
N%932 = 19
N%933 = 589
N%934 = 905
N%935 = 1
N%936 = 235
N%937 = 847
N%938 = 911
N%939 = 670
N%940 = 271
N%941 = 611
N%942 = 727
N%943 = 775
N%944 = 371
N%945 = 631
N%946 = 1
N%947 = 252
N%948 = 283
N%949 = 1
N%950 = 11
N%951 = 868
N%952 = 715
N%953 = 803
N%954 = 289
N%955 = 51
N%956 = 51
N%957 = 1
N%958 = 917
N%959 = 449
N%960 = 451
N%961 = 190
N%962 = 1
N%963 = 325
N%964 = 483
N%965 = 771
N%966 = 85
N%967 = 870
N%968 = 67
N%969 = 562
N%970 = 1
N%971 = 450
N%972 = 415
N%973 = 701
N%974 = 19
N%975 = 586
N%976 = 851
N%977 = 878
N%978 = 25
N%979 = 210
N%980 = 771
N%981 = 838
N%982 = 101
N%983 = 341
N%984 = 283
N%985 = 966
N%986 = 1
N%987 = 694
N%988 = 391
N%989 = 775
N%990 = 1
N%991 = 917
N%992 = 35
N%993 = 1
N%994 = 309
N%995 = 111
N%996 = 943
N%997 = 937
N%998 = 563
N%999 = 334

Scholtz · October 20, 2017, 2:53pm

pre A%3 = 1 && A%4=3 && N%A = 1 …

N%7 = 1
N%43 = 1
N%55 = 1
N%91 = 1
N%127 = 1
N%187 = 1
N%259 = 1
N%319 = 1
N%331 = 1
N%511 = 1
N%559 = 1
N%595 = 1
N%679 = 1
N%715 = 1
N%1015 = 1
N%1243 = 1
N%1591 = 1
N%1651 = 1
N%1687 = 1
N%2035 = 1
N%2359 = 1
N%2431 = 1
N%2827 = 1
N%3139 = 1
N%3367 = 1
N%3451 = 1
N%3655 = 1
N%3955 = 1
N%4015 = 1
N%4147 = 1
N%4171 = 1
N%4303 = 1
N%4699 = 1
N%4711 = 1
N%5335 = 1
N%6235 = 1
N%6643 = 1
N%6919 = 1
N%7735 = 1
N%8827 = 1
N%8995 = 1
N%9271 = 1

jsuchal · October 20, 2017, 3:08pm

Ja sa uz trosku stracam. Nevedeli by pomoc chalani od @Dusan_Klinec ?

Sveto · October 20, 2017, 3:37pm

aby sa nestlo ze to @Scholtz hackne s excelom alebo kalkulackou

rho · October 20, 2017, 3:44pm

msieve.zip (19.1 KB)
Pls. checkni parametre factmsieve.py v prilozenom baliku na upravu toho intervalu hladania prvocisiel. Viac informacii asi teraz v predstihu este nebudeme mat
Potom spustim a dam estimaciu co hlasi K80 tesla.

rho · October 20, 2017, 4:35pm

Ok, takze pre priblizne estimacie co to dokaze s GPU
Faktorizoval som taketo nieco (100digit = 800b)
2881039827457895971881627053137530734638790825166127496066674320241571446494762386620442953820735453
nebol to brute force, ale gnfs faktorizacia s pouzitim GPU Tesla K60 a 6 CPU server
vysledok
p45 factor: 618162834186865969389336374155487198277265679
p55 factor: 4660648728983566373964395375209529291596595400646068307
dlzka trvania - 1 hodina 5 minut
priblizna cena ktoru ma to stalo v Azure - 0,8 EUR
good luck

Dusan_Klinec · October 20, 2017, 5:03pm

800b ? Uvedeny modulus ma 331 bitov.

rho · October 20, 2017, 5:06pm

to bol iba test
ale uz znasilnujem suchalove N

DHlavaty · October 22, 2017, 9:33am

Akosi nechápem, čo sa snažíte faktorizovať/hackovať.

Veľmi pozorne som si prečítal dostupné materiály ( https://crocs.fi.muni.cz/public/papers/rsa_ccs17 ; https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf aj niektoré tam spomínané staršie zraniteľnosti). No samotná ROCA zraniteľnosť ešte nebola zverejnená, bude až 2. novembra 2017. Jediné čo teraz môžete, je útok hrubou silou (aj keď asi v mierne obmedzenom priestore p a q) A to je zatiaľ stále nepraktické. Alebo už viete niekto niečo viac o slabine ?

Jedine že by ste sami našli zraniteľnosť v dátach, ktoré sú od augusta 2016 zverejnené na https://crocs.fi.muni.cz/public/papers/usenix2016 (linky dole na stránke)

Budem rád ak ma opravíte prípadne poskytnete dáta.

Ako/čím sa snažíte faktorizovať ? (Ja som sa krypto už niekoľko rokov nevenoval) Už len vypočítať N ^ (1/2) nie je na kalkulačku. Robíte to v tom python-e, čo je tu aj vyššie spominaný ?

rho použil asi ten python, však? Ako to skúšaš ty Scholz, keď si písal: “Moj noteboook mi dava N.mod(iter) == 0 test 5300x za sekundu na single threade” ?

Ja by som to osobne asi kvôli rýchlosti skúšal v GOlangu (skúsim to neskôr a dám vedieť). Všetky tipy rád uvítam.

rho · October 22, 2017, 1:03pm

Už teraz možem povedať ze msieve knižnica sa na to nehodí a jej gpu akcelerácia je nepodstatná pre tuto úlohu.
Môj skromný cieľ v tomto “challenge” je optimalizovať resp. zrýchliť metódami sw inžinierstva ten hrozivý odhad 20-40 tis.

jsuchal · October 22, 2017, 9:13pm

Tak podla nazvu papera / utoku by som cakal, ze to bude skor nejaka takato finta. https://cryptologie.net/article/222/implementation-of-coppersmith-attack-rsa-attack-using-lattice-reductions/

DHlavaty · October 23, 2017, 10:21am

Skusil som jednoduchy N.mod(iter) == 0 test v GOlang. Na mojom notebooku (Intel i7 2,5 Ghz) dava 1 041 600 za sekundu.

Zdrojak: https://play.golang.org/p/qqRQoYet3_ (samozrejme si to nepustajte vo webovom playgrounde ale na masine). Mne to tych 100 milionov dalo za 48 sekund.

UPDATE: Kto chcete prispievat, kludne aj tu https://gist.github.com/dhlavaty/a8ea12423a3f8292da0d66e0b2b02dd2

DHlavaty · October 23, 2017, 11:20am

Kedze v golang sa krasne robi multi-threadovo, spravil som aj multithread verziu. Na mojej i7 ma teoreticky zmysel 8 threadov (co som si aj overil testom). Dostal som sa na 5 milionov N.mod(iter) == 0 za sekundu.

Aj multithread verziu najdete tu: https://gist.github.com/dhlavaty/a8ea12423a3f8292da0d66e0b2b02dd2

jsuchal · October 23, 2017, 11:22am

To je pekne, ale cistym bruteforcom to podla mna nedas, kym nemas celoplanetarny botnet k dispozicii. Kukni ten clanok hore. To uz je nad moje chapanie, ale tada nejako pojde cesta.

DHlavaty · October 23, 2017, 11:26am

Veď ako som písal hore, zatiaľ zraniteľnosť nebola zverejnená - preto nechápem čo tu chcete faktorizovať.

Ja som to v tom golang skúšal vyslovene len ako benchmark. Robiť brute-force určite nejdem.

Scholtz · October 23, 2017, 11:27am

Cau, ja som to robil v c#, bez cuda, …

Issue je v tom, ze N % i je podstatne narocnejsie pre vecsie N…

To si mal co na mysli? Faktorizovat cislo 2881039827457…735453 ?

Ja som sa pokusil najst niekde daku biginteger kniznicu tak aby som si ju vedel upravit a vypocty fungovali priamo na gpu… Predbezne som sa dostal na mojom notebooku na 1 miliardu operaciu za sekundu ale zatial iba pre mensie mod…

Inac takato kniznica by sa dala optimalizovat tym, ze sa predpocitaju zakladne modulo a potom to ide rychlejsie… ale npr modulo na 8 bit zabere 256*256 256 * 8 bajtov pamete co je 134.217.728 B… Otestoval som to zatial na 7bit 128128 * 128 * 8 = 16.777.216 B a vyzera ze je to podstatne rychlejsie ako standardne modulo procesorom…

DHlavaty · October 23, 2017, 11:29am

Scholtz > Pozri zdroják. Je fakt jednoduchý. A faktorizujem v ňom priamo Suchalove N