Silny problem RSA
W kryptologii w teorii liczb , problemem RSA ( silnego RSA ) jest znalezienie pierwiastka e- th podanej liczby w pierścieniu . Została wprowadzona niezależnie przez Baricia i Pfitzmanna oraz Fujisaki i Okamoto w 1997 roku jako hipoteza obliczeniowa w celu udowodnienia bezpieczeństwa konstrukcji kryptograficznych, w szczególności podpisów cyfrowych . To złagodzenie problemu RSA daje bardziej wydajne podpisy i eliminuje potrzebę pewnych wyidealizowanych modeli, takich jak przypadkowa wyrocznia w dowodzie bezpieczeństwa.
Definicja
Niech będą dwiema różnymi liczbami pierwszymi i rozważmy pierścień ilorazowy . Silny problem RSA polega na znalezieniu, podanych i , dwóch liczb całkowitych i tym podobnych .
p,q{\ displaystyle p, q}
nie=pq{\ displaystyle n = pq}
R=Z/(nie){\ Displaystyle R = \ mathbb {Z} / (n)}
nie{\ displaystyle n}
y∈R∖{0}{\ displaystyle y \ in R \ setminus \ {0 \}}
x∈R{\ Displaystyle x \ w R}
mi∈NIE∖{0,1}{\ Displaystyle e \ in \ mathbb {N} \ setminus \ {0,1 \}}
xmi=y{\ Displaystyle x ^ {e} = y}![{\ Displaystyle x ^ {e} = y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f011af7832a39b13af46b433ada2d0e06d7ccf1b)
Silny problem RSA jest a priori łatwiejszy niż standardowy problem RSA , ponieważ w zasadzie możemy dowolnie wybierać e .
Obecnie (2018) najlepszym znanym sposobem rozwiązania problemu silnego RSA (zgodnie z normą problemu RSA) jest uzyskanie na czynniki o . Rzeczywiście, biorąc pod uwagę taką faktoryzację, łatwo jest znaleźć dwie liczby całkowite, takie jak gdzie jest funkcja Eulera , za pomocą algorytmu Euclid . Wnioskujemy natychmiast . Nie jest jednak wykluczone, że istnieją określone algorytmy rozwiązujące silny problem RSA bez uzyskania faktoryzacji .
nie{\ displaystyle n}
mi,re{\ displaystyle e, d}
mire=1modφ(nie){\ displaystyle ed = 1 {\ bmod {\ varphi}} (n)}
φ{\ displaystyle \ varphi}
x=yre{\ Displaystyle x = y ^ {d}}
nie{\ displaystyle n}![nie](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Ważne przykłady
- Zabezpieczenie podpisów Gennaro-Halevi-Rabina przed egzystencjalnymi fałszerstwami zostało zredukowane w Modelu Standardowym do silnego problemu RSA.
- Bezpieczeństwo podpisów Cramer-Shoup można udowodnić w Modelu Standardowym, opierając się na silnym problemie RSA.
Uwagi i odniesienia
Uwagi
-
Odnajdujemy również nazwę elastycznego problemu RSA (w języku angielskim: elastyczny problem RSA ), która jest jednak znacznie rzadziej używana w literaturze.
Bibliografia
-
(w) Ronald L. Rivest i Burt Kaliski , „RSA Problem” , w Encyclopedia of Cryptography and Security , Springer US,2005( ISBN 9780387234731 , DOI 10.1007 / 0-387-23483-7_363 , czytaj online ) , s. 532–536
-
(w) Dan Boneh , „Strong RSA Assumption” , w Encyclopedia of Cryptography and Security , Springer US,2005( ISBN 9780387234731 , DOI 10.1007 / 0-387-23483-7_414 , czytaj online ) , s. 597–597
-
(w) Niko Barić i Birgit Pfitzmann , „Collision-Free Accumulators and Fail-stop Signature Schemes Without Trees” in Advances in Cryptology - EUROCRYPT '97 , Springer Berlin Heidelberg,1997( ISBN 9783540629757 , DOI 10.1007 / 3-540-69053-0_33 , czytaj online ) , str. 480–494
-
(w) Eiichiro Fujisaki i Tatsuaki Okamoto , "Statystyczne protokoły wiedzy zerowej To udowodnić modularne relacje wielomianowe" , w Advances in Cryptology - CRYPTO '97 , Springer Berlin Heidelberg,1997( ISBN 9783540633846 , DOI 10.1007 / bfb0052225 , czytaj online ) , str. 16–30
-
(w) Dan Boneh , „Bezpieczne podpisy z założenia„ silnego RSA ” w Encyclopedia of Cryptography and Security , Springer US,2005( ISBN 9780387234731 , DOI 10.1007 / 0-387-23483-7_374 , czytaj online ) , s. 546–546
-
(en) Ronald Cramer i Victor Shoup , „ Signature schematy oparte na założeniu silnego RSA ” , CCS '99 Proceedings of the 6th ACM Conference on Computer and Communication Security , ACM,1 st listopad 1999, s. 46–51 ( ISBN 1581131488 , DOI 10.1145 / 319709.319716 , czytaj online , dostęp: 22 sierpnia 2018 )
-
(w) Marc Joye , „ How (Not) to design strong-RSA signatures ” , Designs, Codes and Cryptography , vol. 59, n kość 1-3,22 grudnia 2010, s. 169-182 ( ISSN 0925-1022 i 1573-7586 , DOI 10.1007 / s10623-010-9453-1 , czytaj online , dostęp: 22 sierpnia 2018 )
-
(w) Dennis Hofheinz , Tibor Jager i Eike Kiltz , „Short signatures from Weaker Assumptions” , w: Lecture Notes in Computer Science , Springer Berlin Heidelberg,2011( ISBN 9783642253843 , DOI 10.1007 / 978-3-642-25385-0_35 , czytaj online ) , str. 647–666
-
(w) David Naccache David Pointcheval i Jacques Stern , „ Rok podwójnych podpisów alternatywny dla paradygmatu hash-and-sign ” , CCS '01 Proceedings of the 8th ACM Conference on Computer and Communications Security , ACM,5 listopada 2001, s. 20–27 ( ISBN 1581133855 , DOI 10.1145 / 501983.501987 , czytaj online , dostęp: 22 sierpnia 2018 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">