înregistrare Logare
Puncte:2
xXLeoXxOne avatar Crypto

Factorizarea unui modul RSA date părți ale unui factor

drapel vn
xXLeoXxOne

e,N,c și aproximativ 2/3 din p sunt date și trebuie să fac întregul p pentru a decripta c.

N: 8319209622572147564013826542514259498682642243858419574823720424163091461701501360015982209990033336520746744572035014978885083880306655150878826112698449183627604378591045476163815683140601440141181336500755042065319357073688047689369842069576880590382907166998622533395350509313527264108988375924505750514907811200521771091619671861896277515872762861803861776874814818759550176763409337645914659855794895018341028254707583446748584671147839997360735893784761893682319714306096295255392779139228496862261602629668021770766403895493829479280751919607803462139336221636202936115853250410851992088076115853781819064537
e: 65537
c: 4953284236047971172578832583499377493178200304479143209550787249372461101728658773670930238470955483017914105971816965742510454042292225833646213980243990906909055183035487729211063154361995845063984656265718117973811054592839102686638618059351593068564821438986641302188691512194069434490636627580791763494578169497869477621620646090488263145323524094255076603309311346040499379850098705597815946140397825326676093352260642665202907180660054018022276329942694463490417145273018047785653000749283804947161814490990395826461165462311565059508939959327500584807568342952319675042226613334756078721555811790191840438113
p: 4657466126792836973364876345509106305470210556754730583762574018947035473615496183374866399186?????????????????????????????? ????????????????????????????????????????????????????????? ???50971895450729845918308008641046893031812864235423521253112739699191715148131622067631404316003898

"?" sunt cifrele lipsă. Am încercat deja să folosesc acest site: https://latticehacks.cr.yp.to/rsa.html dar primesc doar erori (am folosit SageMath pentru asta) cu acele numere, dar exemplul funcționează.

Ce greșesc și mă poate ajuta cineva să găsesc întregul factor pentru a obține cheia?

159
0 + 0
drapel et
user93353
Răspunde asta la întrebarea ta? [Factorizarea unui modul RSA cu biți mari ai unui factor](https://crypto.stackexchange.com/questions/35829/factoring-an-rsa-modulus-given-high-bits-of-a-factor)
3
Răspunde
xXLeoXxOne avatar
drapel vn
xXLeoXxOne
Asta nu o rezolvă, deoarece metoda/algoritmul respectiv funcționează numai dacă aveți mai mult de jumătate din factor cred (prima jumătate). În cazul meu, îmi lipsește mijlocul factorului, așa că am o treime din cifrele de început și o treime din cifrele de la sfârșit.
0
Răspunde
Myria avatar
drapel in
Myria
Care este numărul $c$?
1
Răspunde
xXLeoXxOne avatar
drapel vn
xXLeoXxOne
c este mesajul criptat
0
Răspunde
drapel cn
j.p.
Puteți arunca o privire la tutorialul foarte frumos [Recuperarea cheilor criptografice din informații parțiale, de exemplu](https://ia.cr/2020/1506) de Gabrielle De Micheli și Nadia Heninger.
3
Răspunde
xXLeoXxOne avatar
drapel vn
xXLeoXxOne
Mulțumiri! Ajută puțin, dar este destul de greu de citit... Cazul meu ar trebui să fie pentru metoda Multivariate Coppersmith, nu?
0
Răspunde
drapel cn
j.p.
M-aș aștepta să puteți utiliza metoda lui Coppersmith în mod direct, deoarece există o singură bucată de biți necunoscută. Multivariat de care aveți nevoie doar pentru mai multe bucăți. Nu am rezolvat detaliile, dar aș fi surprins dacă o adaptare a ideilor din secțiunile 4.2.2 și 4.2.3 la cazul dvs. nu ar fi posibilă.
0
Răspunde
Puncte:6
avatar Crypto
drapel pe
Samuel Neves

Problema aici este că ai un divizor $p$ de $n$ a formei $$ p_h \cdot 10^{208} + p_m\cdot 10^{108} + p_l\,, $$ unde stii $p_h$ și $p_l$, dar nu $p_m < 10^{100} \mai puținaprox n^{0,16}$.

În mod clar, polinomul $f(x) = x\cdot 10^{108} + p_h \cdot 10^{208} + p_l$ va fi $0$ modulo $p$ pentru dreapta $x = p_m$, despre care se știe că este mic. Deci putem aplica aici Generalizare GCD a teoremei Coppersmith cu $\beta \aproximativ 0,5$:

sage: p_h = 4657466126792836973364876345509106305470210556754730583762574018947035473615496183374868299
sage: p_l = 5097189545072984591830800864104689303181286423542352125311273969919171514813162206763603401815311273969919171514813162206763194081
sage: n = 8319209622572147564013826542514259498682642243858419574823720424163091461701501360015982209990033336520746744572035014978885083880306655150878826112698449183627604378591045476163815683140601440141181336500755042065319357073688047689369842069576880590382907166998622533395350509313527264108988375924505750514907811200521771091619671861896277515872762861803861776874814818759550176763409337645914659855794895018341028254707583446748584671147839997360735893784761893682319714306096295255392779139228496862261602629668021770766403895493829479280751919607803462139336221636202936115853250410851992088076115853781819064537
sage: P.<x> = Zmod(n)[]
salvie: f = x*10^108 + p_h*10^208 + p_l
sage: f = (x*10^108 + p_h*10^208 + p_l)/10^108 # Faceți polinomul monic
sage: f.small_roots(beta=0,49)
[4555790634870609108348440239954454001363406634260834115187291781797769149826662476501530037260834115187291781797769149826662476501530037258685]
0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.