1258:
201:
Just as there are no proofs that integer factorization is computationally difficult, there are also no proofs that the RSA problem is similarly difficult. By the above method, the RSA problem is at least as easy as factoring, but it might well be easier. Indeed, there is strong evidence pointing to
202:
this conclusion: that a method to break the RSA method cannot be converted necessarily into a method for factoring large semiprimes. This is perhaps easiest to see by the sheer overkill of the factoring approach: the RSA problem asks us to decrypt
375:, David Naccache and Emmanuel Thomé, 2007. This Asiacrypt 2007 paper (link is to a preprint version) proves that solving the RSA problem using an oracle to some certain other special cases of the RSA problem is easier than factoring.
68:(in excess of 1024 bits), no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems—both for
1298:
346:
1238:
1068:
698:
210:
arbitrary ciphertexts, and it also allows one to perform arbitrary RSA private-key encryptions. Along these same lines, finding the decryption exponent
408:
1291:
826:
921:
821:
361:, D. Aggarwal and U. Maurer, 2008. This Eurocrypt 2009 paper (link is to a preprint version) proves that solving the RSA problem using a
1501:
1382:
1346:
1284:
550:
1377:
729:
723:
847:
401:
298:
238:
233:
solving the RSA problem directly. To achieve the full strength of the RSA problem, an RSA-based cryptosystem must also use a
465:
1307:
914:
533:
490:
455:
1506:
445:
394:
229:
In addition to the RSA problem, RSA also has a particular mathematical structure that can potentially be exploited
609:
523:
470:
155:
is chosen randomly within that range; to specify the problem with complete precision, one must also specify how
1454:
1424:
1117:
634:
1434:
1341:
518:
907:
775:
708:
1470:
1233:
1188:
1001:
872:
765:
614:
528:
450:
136:
1408:
1372:
1351:
1112:
624:
513:
495:
1449:
1228:
877:
857:
1367:
760:
1218:
1208:
1063:
816:
587:
1475:
1213:
1203:
1006:
966:
959:
949:
944:
770:
417:
255:
32:
954:
852:
703:
642:
577:
281:
Boneh, Dan; Venkatesan, Ramarathnam (1998). "Breaking RSA may not be equivalent to factoring".
234:
163:
are generated, which will depend on the precise means of RSA random keypair generation in use.
1336:
1326:
1321:
1261:
1107:
1053:
718:
475:
432:
250:
175:
69:
206:
arbitrary ciphertext, whereas the factoring method reveals the private key: thus decrypting
1444:
1223:
1147:
629:
440:
166:
The most efficient method known to solve the RSA problem is by first factoring the modulus
345:, D. Brown, 2005. This unrefereed preprint purports that solving the RSA problem using a
8:
986:
735:
362:
1438:
1428:
316:
1092:
1076:
1023:
582:
505:
485:
480:
460:
260:
73:
46:
1276:
1152:
1142:
1013:
842:
785:
713:
599:
294:
1403:
1087:
688:
286:
50:
28:
1480:
1398:
1162:
1082:
1043:
991:
976:
285:. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 59–71.
1495:
1243:
1198:
1157:
1137:
1033:
996:
971:
1193:
1038:
1028:
1018:
981:
930:
882:
862:
372:
116:
57:
20:
1172:
657:
1132:
1102:
1097:
1058:
806:
538:
290:
60:
are not known. Thus, the task can be neatly described as finding the
1122:
560:
112:
1167:
1127:
867:
801:
672:
667:
662:
565:
543:
65:
41:
356:
340:
693:
652:
132:
1048:
811:
178:). The RSA key setup routine already turns the public exponent
186:, and so exactly the same algorithm allows anyone who factors
647:
604:
572:
555:
79:
More specifically, the RSA problem is to efficiently compute
314:
182:, with this prime factorization, into the private exponent
740:
594:
1306:
1069:
Cryptographically secure pseudorandom number generator
241:, to protect against such structural problems in RSA.
64:
roots of an arbitrary number, modulo N. For large RSA
107:). The structure of the RSA public key requires that
378:
358:
Breaking RSA Generically is
Equivalent to Factoring
1493:
313:An algorithm for this is, for example, given in
280:
222:, even though the RSA problem does not ask for
1292:
915:
402:
342:Breaking RSA may be as difficult as factoring
369:When e-th Roots Become Easier Than Factoring
198:can then be decrypted with the private key.
416:
1299:
1285:
922:
908:
409:
395:
263:, whose equivalency to factoring is known
315:Menezes; van Oorschot; Vanstone (2001).
218:computationally equivalent to factoring
1494:
349:is as difficult as factoring provided
1280:
903:
390:
283:Advances in Cryptology – EUROCRYPT'98
170:a task believed to be impractical if
31:private-key operation given only the
27:summarizes the task of performing an
730:Naccache–Stern knapsack cryptosystem
13:
1502:Computational hardness assumptions
1308:Computational hardness assumptions
334:
14:
1518:
1347:Decisional composite residuosity
1257:
1256:
929:
324:Handbook of Applied Cryptography
16:Unsolved problem in cryptography
761:Discrete logarithm cryptography
1118:Information-theoretic security
307:
274:
115:(i.e., a product of two large
1:
365:is as difficult as factoring.
267:
35:. The RSA algorithm raises a
1383:Computational Diffie–Hellman
776:Non-commutative cryptography
7:
1471:Exponential time hypothesis
1234:Message authentication code
1189:Cryptographic hash function
1002:Cryptographic hash function
873:Identity-based cryptography
766:Elliptic-curve cryptography
244:
174:is sufficiently large (see
10:
1523:
1113:Harvest now, decrypt later
143:), and that 0 ≤
1481:Planted clique conjecture
1463:
1450:Ring learning with errors
1417:
1391:
1378:Decisional Diffie–Hellman
1360:
1314:
1252:
1229:Post-quantum cryptography
1181:
937:
899:
878:Post-quantum cryptography
835:
827:Post-Quantum Cryptography
794:
753:
681:
623:
504:
431:
424:
386:
382:
119:), that 2 <
83:given an RSA public key (
1219:Quantum key distribution
1209:Authenticated encryption
1064:Random number generation
1507:Public-key cryptography
1476:Unique games conjecture
1425:Shortest vector problem
1399:External Diffie–Hellman
1214:Public-key cryptography
1204:Symmetric-key algorithm
1007:Key derivation function
967:Cryptographic primitive
960:Authentication protocol
950:Outline of cryptography
945:History of cryptography
771:Hash-based cryptography
418:Public-key cryptography
317:"Public-Key Encryption"
256:RSA Factoring Challenge
1455:Short integer solution
1435:Closest vector problem
955:Cryptographic protocol
363:generic ring algorithm
1342:Quadratic residuosity
1322:Integer factorization
1108:End-to-end encryption
1054:Cryptojacking malware
433:Integer factorization
347:Straight line program
251:Strong RSA assumption
176:integer factorization
70:public-key encryption
1445:Learning with errors
1224:Quantum cryptography
1148:Trusted timestamping
987:Cryptographic nonce
736:Three-pass protocol
353:has a small factor.
91:) and a ciphertext
1368:Discrete logarithm
1352:Higher residuosity
1093:Subliminal channel
1077:Pseudorandom noise
1024:Key (cryptography)
506:Discrete logarithm
291:10.1007/BFb0054117
261:Rabin cryptosystem
74:digital signatures
1489:
1488:
1464:Non-cryptographic
1274:
1273:
1270:
1269:
1153:Key-based routing
1143:Trapdoor function
1014:Digital signature
895:
894:
891:
890:
843:Digital signature
786:Trapdoor function
749:
748:
466:Goldwasser–Micali
300:978-3-540-64518-4
1514:
1404:Sub-group hiding
1315:Number theoretic
1301:
1294:
1287:
1278:
1277:
1260:
1259:
1088:Insecure channel
924:
917:
910:
901:
900:
732:
633:
628:
588:signature scheme
491:Okamoto–Uchiyama
429:
428:
411:
404:
397:
388:
387:
384:
383:
380:
379:
328:
327:
321:
311:
305:
304:
278:
147: <
123: <
51:composite number
1522:
1521:
1517:
1516:
1515:
1513:
1512:
1511:
1492:
1491:
1490:
1485:
1459:
1413:
1409:Decision linear
1387:
1361:Group theoretic
1356:
1310:
1305:
1275:
1266:
1248:
1177:
933:
928:
887:
831:
795:Standardization
790:
745:
728:
677:
625:Lattice/SVP/CVP
619:
500:
446:Blum–Goldwasser
420:
415:
337:
335:Further reading
332:
331:
319:
312:
308:
301:
279:
275:
270:
247:
17:
12:
11:
5:
1520:
1510:
1509:
1504:
1487:
1486:
1484:
1483:
1478:
1473:
1467:
1465:
1461:
1460:
1458:
1457:
1452:
1447:
1442:
1432:
1421:
1419:
1415:
1414:
1412:
1411:
1406:
1401:
1395:
1393:
1389:
1388:
1386:
1385:
1380:
1375:
1373:Diffie-Hellman
1370:
1364:
1362:
1358:
1357:
1355:
1354:
1349:
1344:
1339:
1334:
1329:
1324:
1318:
1316:
1312:
1311:
1304:
1303:
1296:
1289:
1281:
1272:
1271:
1268:
1267:
1265:
1264:
1253:
1250:
1249:
1247:
1246:
1241:
1239:Random numbers
1236:
1231:
1226:
1221:
1216:
1211:
1206:
1201:
1196:
1191:
1185:
1183:
1179:
1178:
1176:
1175:
1170:
1165:
1163:Garlic routing
1160:
1155:
1150:
1145:
1140:
1135:
1130:
1125:
1120:
1115:
1110:
1105:
1100:
1095:
1090:
1085:
1083:Secure channel
1080:
1074:
1073:
1072:
1061:
1056:
1051:
1046:
1044:Key stretching
1041:
1036:
1031:
1026:
1021:
1016:
1011:
1010:
1009:
1004:
994:
992:Cryptovirology
989:
984:
979:
977:Cryptocurrency
974:
969:
964:
963:
962:
952:
947:
941:
939:
935:
934:
927:
926:
919:
912:
904:
897:
896:
893:
892:
889:
888:
886:
885:
880:
875:
870:
865:
860:
855:
850:
845:
839:
837:
833:
832:
830:
829:
824:
819:
814:
809:
804:
798:
796:
792:
791:
789:
788:
783:
778:
773:
768:
763:
757:
755:
751:
750:
747:
746:
744:
743:
738:
733:
726:
724:Merkle–Hellman
721:
716:
711:
706:
701:
696:
691:
685:
683:
679:
678:
676:
675:
670:
665:
660:
655:
650:
645:
639:
637:
621:
620:
618:
617:
612:
607:
602:
597:
592:
591:
590:
580:
575:
570:
569:
568:
563:
553:
548:
547:
546:
541:
531:
526:
521:
516:
510:
508:
502:
501:
499:
498:
493:
488:
483:
478:
473:
471:Naccache–Stern
468:
463:
458:
453:
448:
443:
437:
435:
426:
422:
421:
414:
413:
406:
399:
391:
377:
376:
366:
354:
336:
333:
330:
329:
306:
299:
272:
271:
269:
266:
265:
264:
258:
253:
246:
243:
235:padding scheme
190:to obtain the
15:
9:
6:
4:
3:
2:
1519:
1508:
1505:
1503:
1500:
1499:
1497:
1482:
1479:
1477:
1474:
1472:
1469:
1468:
1466:
1462:
1456:
1453:
1451:
1448:
1446:
1443:
1440:
1436:
1433:
1430:
1426:
1423:
1422:
1420:
1416:
1410:
1407:
1405:
1402:
1400:
1397:
1396:
1394:
1390:
1384:
1381:
1379:
1376:
1374:
1371:
1369:
1366:
1365:
1363:
1359:
1353:
1350:
1348:
1345:
1343:
1340:
1338:
1335:
1333:
1330:
1328:
1325:
1323:
1320:
1319:
1317:
1313:
1309:
1302:
1297:
1295:
1290:
1288:
1283:
1282:
1279:
1263:
1255:
1254:
1251:
1245:
1244:Steganography
1242:
1240:
1237:
1235:
1232:
1230:
1227:
1225:
1222:
1220:
1217:
1215:
1212:
1210:
1207:
1205:
1202:
1200:
1199:Stream cipher
1197:
1195:
1192:
1190:
1187:
1186:
1184:
1180:
1174:
1171:
1169:
1166:
1164:
1161:
1159:
1158:Onion routing
1156:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1138:Shared secret
1136:
1134:
1131:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1109:
1106:
1104:
1101:
1099:
1096:
1094:
1091:
1089:
1086:
1084:
1081:
1078:
1075:
1070:
1067:
1066:
1065:
1062:
1060:
1057:
1055:
1052:
1050:
1047:
1045:
1042:
1040:
1037:
1035:
1034:Key generator
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1015:
1012:
1008:
1005:
1003:
1000:
999:
998:
997:Hash function
995:
993:
990:
988:
985:
983:
980:
978:
975:
973:
972:Cryptanalysis
970:
968:
965:
961:
958:
957:
956:
953:
951:
948:
946:
943:
942:
940:
936:
932:
925:
920:
918:
913:
911:
906:
905:
902:
898:
884:
881:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
854:
851:
849:
846:
844:
841:
840:
838:
834:
828:
825:
823:
820:
818:
815:
813:
810:
808:
805:
803:
800:
799:
797:
793:
787:
784:
782:
779:
777:
774:
772:
769:
767:
764:
762:
759:
758:
756:
752:
742:
739:
737:
734:
731:
727:
725:
722:
720:
717:
715:
712:
710:
707:
705:
702:
700:
697:
695:
692:
690:
687:
686:
684:
680:
674:
671:
669:
666:
664:
661:
659:
656:
654:
651:
649:
646:
644:
641:
640:
638:
636:
631:
626:
622:
616:
613:
611:
608:
606:
603:
601:
598:
596:
593:
589:
586:
585:
584:
581:
579:
576:
574:
571:
567:
564:
562:
559:
558:
557:
554:
552:
549:
545:
542:
540:
537:
536:
535:
532:
530:
527:
525:
522:
520:
517:
515:
512:
511:
509:
507:
503:
497:
496:Schmidt–Samoa
494:
492:
489:
487:
484:
482:
479:
477:
474:
472:
469:
467:
464:
462:
459:
457:
456:Damgård–Jurik
454:
452:
451:Cayley–Purser
449:
447:
444:
442:
439:
438:
436:
434:
430:
427:
423:
419:
412:
407:
405:
400:
398:
393:
392:
389:
385:
381:
374:
370:
367:
364:
360:
359:
355:
352:
348:
344:
343:
339:
338:
325:
318:
310:
302:
296:
292:
288:
284:
277:
273:
262:
259:
257:
254:
252:
249:
248:
242:
240:
236:
232:
227:
225:
221:
217:
213:
209:
205:
199:
197:
193:
189:
185:
181:
177:
173:
169:
164:
162:
158:
154:
150:
146:
142:
138:
134:
130:
126:
122:
118:
117:prime numbers
114:
110:
106:
102:
98:
94:
90:
86:
82:
77:
75:
71:
67:
63:
59:
55:
52:
48:
44:
43:
38:
34:
30:
26:
22:
1331:
1194:Block cipher
1039:Key schedule
1029:Key exchange
1019:Kleptography
982:Cryptosystem
931:Cryptography
883:OpenPGP card
863:Web of trust
780:
519:Cramer–Shoup
373:Antoine Joux
368:
357:
350:
341:
323:
309:
282:
276:
230:
228:
223:
219:
215:
211:
207:
203:
200:
195:
191:
187:
183:
179:
171:
167:
165:
160:
156:
152:
148:
144:
140:
128:
124:
120:
108:
104:
100:
96:
92:
88:
84:
80:
78:
61:
53:
40:
36:
24:
21:cryptography
18:
1332:RSA problem
1182:Mathematics
1173:Mix network
853:Fingerprint
817:NSA Suite B
781:RSA problem
658:NTRUEncrypt
192:private key
111:be a large
25:RSA problem
1496:Categories
1337:Strong RSA
1327:Phi-hiding
1133:Ciphertext
1103:Decryption
1098:Encryption
1059:Ransomware
807:IEEE P1363
425:Algorithms
268:References
33:public key
1123:Plaintext
113:semiprime
66:key sizes
1418:Lattices
1392:Pairings
1262:Category
1168:Kademlia
1128:Codetext
1071:(CSPRNG)
868:Key size
802:CRYPTREC
719:McEliece
673:RLWE-SIG
668:RLWE-KEX
663:NTRUSign
476:Paillier
245:See also
42:exponent
938:General
714:Lamport
694:CEILIDH
653:NewHope
600:Schnorr
583:ElGamal
561:Ed25519
441:Benaloh
231:without
214:indeed
133:coprime
127:, that
58:factors
37:message
1049:Keygen
836:Topics
812:NESSIE
754:Theory
682:Others
539:X25519
297:
194:. Any
103:
56:whose
47:modulo
39:to an
23:, the
1079:(PRN)
648:Kyber
643:BLISS
605:SPEKE
573:ECMQV
566:Ed448
556:EdDSA
551:ECDSA
481:Rabin
320:(PDF)
237:like
848:OAEP
822:CNSA
699:EPOC
544:X448
534:ECDH
295:ISBN
239:OAEP
159:and
72:and
1439:gap
1429:gap
858:PKI
741:XTR
709:IES
704:HFE
635:SIS
630:LWE
615:STS
610:SRP
595:MQV
578:EKE
529:DSA
514:BLS
486:RSA
461:GMR
287:doi
208:all
204:one
151:.
135:to
131:be
101:mod
29:RSA
19:In
1498::
689:AE
524:DH
371:,
322:.
293:.
226:.
216:is
168:N,
95:≡
87:,
76:.
49:a
45:,
1441:)
1437:(
1431:)
1427:(
1300:e
1293:t
1286:v
923:e
916:t
909:v
632:/
627:/
410:e
403:t
396:v
351:e
326:.
303:.
289::
224:d
220:N
212:d
196:C
188:N
184:d
180:e
172:N
161:e
157:N
153:C
149:N
145:C
141:N
139:(
137:φ
129:e
125:N
121:e
109:N
105:N
99:(
97:P
93:C
89:e
85:N
81:P
62:e
54:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.