Kysymys:
Pitäisikö RSA: n julkisen eksponentin olla turvallisuussyistä vain {3, 5, 17, 257 tai 65537}?
Vladislav Rastrusny
2011-03-01 14:59:16 UTC
view on stackexchange narkive permalink

Projektissani käytän julkisen eksponentin 4451h arvoa. Luulin, että se on turvallista ja ok, kunnes aloin käyttää yhtä kaupallista RSA-salauskirjastoa. Jos käytän tätä eksponenttia tämän kirjaston kanssa, se aiheuttaa poikkeuksen.

Otin yhteyttä tämän kirjaston kehittäjiin ja sain seuraavan vastauksen: "Tämän ominaisuuden tarkoituksena on estää joitain RSA-avaimiin kohdistuvia hyökkäyksiä. Seurauksena on, että eksponentti arvo on rajoitettu arvoon {3, 5, 17, 257 tai 65537}. Tämän tarkastuksen poistamista tutkitaan edelleen, koska riskit voivat olla suuret. "

Kuulen, että arvot ovat ensimmäistä kertaa elämässäni muita kuin {3, 5, 17, 257 tai 65537} käytetään RSA: n hajottamiseen. Tiesin vain 3: n käyttämisen väärin täytetyillä haavoittuvuuksilla.

Onko niin? Voin varmasti käyttää toista kirjastoa, mutta vastaukseni jälkeen huolestuin ratkaisuni turvallisuudesta.

Kuusi vastused:
#1
+69
Thomas Pornin
2011-03-01 18:13:06 UTC
view on stackexchange narkive permalink

RSA: lla ei ole tunnettua heikkoutta lyhyelle tai pitkälle julkiselle eksponentille, kunhan julkinen eksponentti on "oikea" (ts. suhteellisen alkuarvona arvoon p-1 kaikille alkukappaleille p jotka jakavat moduulin).

Jos käytät pientä eksponenttia ja , et käytä salausta ja salaat täsmälleen saman viestin useilla erillisillä julkisilla avaimilla, viesti on vaarassa: jos e = 3 , ja salaat viestin m julkisilla avaimilla n1 , n2 ja n3 , niin sinulla on c i = m 3 mod ni kohteelle i = 1 - 3 . Kiinan jäännöslauseen avulla voit sitten rakentaa uudelleen m3 modin n 1 n 2 n 3 , joka osoittautuu m3 (ilman moduulia), koska n 1n2n3 on suurempi kokonaisluku. (Ei modulaarinen) kuutiojuuren poiminta riittää sitten m.

Tässä heikkoutena ei ole pieni eksponentti; pikemminkin se on väärän pehmusteen käyttö (nimittäin ei täyttöä lainkaan) salaukseen. Täyte on erittäin tärkeä RSA: n turvallisuuden kannalta, olipa kyseessä salaus tai allekirjoitus; Jos et käytä asianmukaista pehmustetta (kuten PKCS # 1 kuvatut), sinulla on monia heikkouksia, eikä edellisessä kappaleessa kuvattu ole ylivoimaisesti suurin. Kuitenkin aina kun joku viittaa eksponenttikokoon liittyvään heikkouteen, hän viittaa enemmän tai vähemmän suoraan tähän tapahtumaan. Se on vähän vanhaa ja väärää opetusta, joka joskus käännetään kielloksi isoille eksponenteille (koska se on myytti, käänteinen myytti on myös myytti, eikä se ole enää - eikä vähempää - - perusteltu) Uskon, että tämä on se, mitä havaitset täällä.

Voidaan kuitenkin löytää muutama syy, miksi isoa julkista eksponenttia vältetään:

  • Pienet julkiset eksponentit edistävät tehokkuutta (julkisen avaimen operaatioissa).

  • Pienellä yksityisellä eksponentilla on tietoturvaongelmia. ; avaimen palautushyökkäys on kuvattu, kun yksityisen eksponentin pituus on enintään 29% julkisen eksponentin pituudesta. Kun haluat pakottaa yksityisen eksponentin olemaan lyhyt (esim. Yksityisen avaimen operaatioiden nopeuttamiseksi), sinun on käytettävä enemmän tai vähemmän isoa julkista eksponenttia (yhtä suuri kuin moduuli); Julkisen eksponentin vaatiminen lyhyeksi voidaan sitten nähdä eräänlaisena epäsuorana vastatoimenpiteenä.

  • Jotkut laajalti käyttöönotetut RSA-toteutukset tukehtuvat suuriin RSA-julkisiin eksponenteihin. Esim. Windowsin RSA-koodi (CryptoAPI, jota Internet Explorer käyttää HTTPS: lle) vaatii koodaamaan julkisen eksponentin yhdellä 32-bittisellä sanalla; se ei voi käsitellä julkista avainta suuremmalla julkisella eksponentilla.

Silti "riskit voivat olla suuria" näyttää yleiseltä perustelulta ("tämä on turvallisuuskysymys" on tavanomainen tapa sanoa "emme toteuttaneet sitä, mutta emme halua myöntää minkäänlaista laiskuutta").

Erittäin hyvin sanottu. IIRC, jossain vaiheessa monissa inkarnaatioissaan, PGP käytti generoimaan satunnaisen 16-bittisen julkisen eksponentin avaimen luomisen aikana.
Upeassa kehityksessä tätä viestiä käytetään nyt perustelemaan 1: n käyttö julkisena eksponenttina https://github.com/saltstack/salt/commit/5dd304276ba5745ec21fc1e6686a0b28da29e6fc#commitcomment-3525158
Jälkipolvien vuoksi.Avaimen palautushyökkäystä, jota käytetään käytettäessä pientä yksityistä eksponenttia (tai suurta julkista eksponenttia), kutsutaan [Wienerin hyökkäykseksi] (https://en.wikipedia.org/wiki/Wiener's_attack).
#2
+22
D.W.
2011-03-02 12:11:52 UTC
view on stackexchange narkive permalink

Kehittäjät ovat yksinkertaisesti virheellisiä. Eksponentissa 0x4451 (desimaali 17489) ei ole mitään vikaa; se ei aiheuta turvallisuusongelmia.

Jo kauan sitten ihmiset ajattelivat, että pienet eksponentit olivat ongelma johtuen hyökkäyksestä, jonka Thomas Pornin selitti lähettämällä saman viestin useille vastaanottajille. Mutta tänään ymmärrämme, että eksponenteilla ei ollut mitään tekemistä sen kanssa; ongelma oli väärä pehmuste. Nämä hyökkäykset estetään täytteen asianmukaisella käytöllä. Mikä tahansa salauksen arvoinen salauskirjasto oli varmaan parempi käyttää oikeaa täytettä (muuten sinulla on paljon pahempia ongelmia).

Salauskirjastolle ei siis ole mitään hyvää syytä kieltää ehdottomasti kyseisen eksponentin käyttöä.

Suorituskyvyn näkökulmasta katsottuna mitä pienempi eksponentti, sitä parempi suorituskyky. Paras valinta on e = 3, koska se antaa parhaan suorituskyvyn eikä sillä ole tunnettuja turvallisuusongelmia. (Itse asiassa e = 2 on jopa hieman parempi. Se tunnetaan myös nimellä Rabin-salaus. Järjestelmä ei kuitenkaan ole yhtä tunnettu ja vaatii hieman erilaista koodia, joten sitä ei käytetä laajalti.)

Oletko varma, että "e = 2 on jopa hieman parempi" koskee RSA: ta? Kun e = 2, käänteistä ei ole, koska phi (N) on tasainen.
@Yifan, voit aloittaa lukemalla https://en.wikipedia.org/wiki/Rabin_cryptosystem.
Rabinille salauksen purku on: m = sqrt (c) mod N, annettu c = m ^ 2 mod N. RSA: lle salauksen purku on: m = c ^ d mod N, annettu c = m ^ e mod N. Jos e = 2, ei ole käänteistä modi phi (N) (koska 2 ja phi (N) eivät ole suhteellisen prime), joten et löydä sellaista mainosta, että e * d = 1 mod phi (N).
@Yifan, kyllä, ymmärrän kaiken. En ole varma, mihin olet menossa tämän kanssa. Sanon, että Rabin, jossa e = 2, on vielä hieman parempi kuin RSA, jossa e = 3. Ei, Rabin, jonka e = 2, ei ole sama kuin RSA, mutta erot ovat yksityiskohtia, jotka eivät kuulu tämän kysymyksen piiriin.
Okei, se on selitys, jonka halusin. Harjoittamattomalle silmälle vastauksesi tarkoittaa, että voit valita e = 2 RSA: lle.
#3
+19
aaz
2011-03-01 00:39:39 UTC
view on stackexchange narkive permalink

Nämä viisi numeroa ovat Fermat-primejä.

Koska ne ovat muodossa 2 k + 1, salaus on me = m · ((( m 2 sup>) 2 ... k kertaa ...) 2 , joka on yksinkertaisempaa ja nopeampaa kuin eksponentti samankokoisen eksponentin kanssa yleisessä tapauksessa.

Koska ne ovat primejä, testi, johon e on sopiva ( p - 1) ( q - 1) on vain testi, jota e ei jaa.

Tämä on siis todennäköisempää nopeudesta tai sopimuksesta kuin turvallisuudesta. Ei, että tehokkuudessa ei ole mitään vikaa. Mutta varmista, että kysy viittausta muun vastauksen ehdotuksen mukaisesti.

Katso myös tämä viesti.

#4
+8
Accipitridae
2011-02-28 23:56:07 UTC
view on stackexchange narkive permalink

En ole tietoinen mistään syystä, miksi RSA-avaimen julkisen eksponentin pitäisi olla vain joukossa {3,5,17,257,65537}. Kuten mainitsitte, pienten eksponenttien, kuten 3 tai 5, käyttö on riskialtista, koska toteutusvirheiden (kuten väärän täytön) kielteiset vaikutukset voivat olla suurempia. NIST sallii vain julkiset eksponentit, jotka ovat suurempia kuin 2 ^ 16, mutta en tiedä syytä heidän päätökselleen.

Sinun ei pitäisi olla tyytyväinen käyttämäsi ja kysyttävän kirjaston kehittäjien antamaan vastaukseen. konkreettiseksi viitteeksi. Liian usein käy ilmi, että jotakin paperia ymmärrettiin väärin. Voisin esimerkiksi kuvitella, että joku kehittäjä lukee Phong Nguyenin julkaisun "Voimmeko luottaa kryptografisiin ohjelmistoihin? Salausvirheet GNU Privacy Guard v1.2.3 -ohjelmassa" osion 4 ja tekee virheellisen johtopäätöksen, kuten yllä olevan. Tämä artikkeli huomaa, että kun GnuPG: n tuottama julkinen avain osoittautuu epätavalliseksi arvoksi, kuten 65539, hyökkääjä oppii vähän tietoa salaisesta avaimesta. Johtopäätöksenä on, että GnuPG: n avaimen luontialgoritmia voitaisiin parantaa, mutta ei sitä 65539 on huono julkinen avain.

#5
+7
Andreas Arnold
2011-03-01 15:43:26 UTC
view on stackexchange narkive permalink

En löytänyt viitteitä siitä, että muut julkisen eksponentin arvot ovat haavoittuvia. Julkisen eksponentin kova käyttö lähellä voimaa 2 on suositeltavaa suorituskykysyistä RSA.com -oppaassa RSA-algoritmille

Wikipedian mukaan, NIST ei salli julkista eksponenttia, joka on pienempi kuin 65537, koska pienemmät eksponentit ovat ongelma, jos niitä ei ole kunnolla täytetty.

Osoittautuu, että vastauksen viimeinen kappale on väärä. (Wikipedia on väärässä; kuvittele sitä!) Ongelmalla ei ole mitään tekemistä pienten eksponenttien kanssa. Jos et käytä asianmukaista pehmustetta, olet niin ruuvattu (ja tämä on totta riippumatta siitä, mitä eksponenttia käytät). Jos käytät oikeaa pehmustetta, pienet eksponentit ovat yhtä hyviä kuin suuret. Joten on väärinkäsitys ajatella, että tällä on mitään tekemistä eksponentin koon kanssa, toisin kuin oikean täytteen olemassaolo / puuttuminen.
Kuten sanoin, riittämätön pehmuste. Tarkistin kuitenkin Wikipedia-lauseen lähteen, ja se on osittain väärä. SP 800-78 -3: n (http://csrc.nist.gov/publications/nistpubs/800-78-3/sp800-78-3.pdf) mukaan sivu 6: "Tämä eritelmä rajoittaa myös RSA-eksponentti, joka voi liittyä PIV-avaimiin. Tämän spesifikaation toteutusten on valittava eksponentti, joka on pariton positiivinen kokonaisluku, joka on suurempi tai yhtä suuri kuin 65 537 ja pienempi kuin 2256, kuten taulukossa 3-2 on määritelty. Joten vain PIV-avaimet (Personal Identity Verification) FIPS 201: n mukaan.
#6
-2
FaST4
2018-02-01 15:39:26 UTC
view on stackexchange narkive permalink

Lainaten Don Coppersmithin vuoden 1997 paperia "Pienet ratkaisut polynomiyhtälöihin ja alhaisen eksponentin RSA-haavoittuvuudet":

RSA-salaus eksponentilla 3 on haavoittuva, jos vastustaja tietää kaksi kolmasosaa viestistä .

Vaikka tämä ei välttämättä ole ongelma, jos käytetään RSA-OAEP-pehmustemallia, PKCS # 1 -pehmustemalli (joka annetaan asianmukaisena täytemallina alla olevissa vastauksissa) on haavoittuva jos käytetään julkista eksponenttia 3.

Tämä ei ole aivan vastaus.Osoitat vain yhtä eksponenttia, ja vuosia ennen sinun vastauksiasi on julkaistu muita vastauksia, jotka näyttävät jo käsittelevän tätä ongelmaa paljon yksityiskohtaisemmin.Alamäet eivät välttämättä tarkoita, että olet väärässä.Alamäet voivat tarkoittaa yksinkertaisesti sitä, että vastauksesi ei ole "hyödyllinen" (työkaluvihjeen mukaan), mihin olen samaa mieltä tässä tapauksessa.
Edellisessä vastauksessa todetaan, että "RSA: n lyhyelle tai pitkälle julkiselle eksponentille ei ole tunnettua heikkoutta", mikä on tosiasiallisesti virheellinen.Sitä vastauksessani yritetään tuoda esiin.
Joten, tämä on vastaus toiseen vastaukseen?
Jos mielestäsi hyväksytty vastaus on väärä, lähetä kommentti vastaukseen.Olen varma, että Pornin on enemmän kuin tarpeeksi asiantuntija arvioidakseen.


Tämä Q & A käännettiin automaattisesti englanniksi.Alkuperäinen sisältö on saatavilla stackexchange-palvelussa, jota kiitämme cc by-sa 2.0-lisenssistä, jolla sitä jaetaan.
Loading...