3654:(even when challenge messages are chosen uniformly at random from the message space). By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts this specific chosen-ciphertext attack, since the decryption algorithm then only produces the root that the attacker already knows. If this technique is applied, the proof of the equivalence with the factorization problem fails, so it is uncertain as of 2004 if this variant is secure. The
4982:
1187:
2510:
3603:. Thus, Rabin decryption for random plaintext is at least as hard as the integer factorization problem, something that has not been proven for RSA. It is generally believed that there is no polynomial-time algorithm for factoring, which implies that there is no efficient algorithm for decrypting a random Rabin-encrypted value without the private key
893:
3541:, to eliminate this problem. A way of removing the ambiguity of inversion was suggested by Blum and Williams: the two primes used are restricted to primes congruent to 3 modulo 4 and the domain of the squaring is restricted to the set of quadratic residues. These restrictions make the squaring function into a
53:
proven to be as hard as factoring integers, while there is no such proof known for the RSA trapdoor function. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to
3536:
If the plaintext is intended to represent a text message, guessing is not difficult; however, if the plaintext is intended to represent a numerical value, this issue becomes a problem that must be resolved by some kind of disambiguation scheme. It is possible to choose plaintexts with special
2262:
3646:
attacks since the process of encryption is deterministic. An adversary, given a ciphertext and a candidate message, can easily determine whether or not the ciphertext encodes the candidate message (by simply checking whether encrypting the candidate message yields the given ciphertext).
54:
identify which of the four possible inputs was the true plaintext. Naive attempts to work around this often either enable a chosen-ciphertext attack to recover the secret key or, by encoding redundancy in the plaintext space, invalidate the proof of security relative to factoring.
719:
3532:
Decrypting produces three false results in addition to the correct one, so that the correct result must be guessed. This is the major disadvantage of the Rabin cryptosystem and one of the factors which have prevented it from finding widespread practical use.
1690:
1182:{\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}
2505:{\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}
2083:
1982:
2252:
577:
4079:
Scott
Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug
1874:
3516:
2267:
898:
582:
57:
Public-key encryption schemes based on the Rabin trapdoor function are used mainly for examples in textbooks. In contrast, RSA is the basis of standard public-key encryption schemes such as
1288:
839:
3419:
2840:
1491:
3470:
2590:
1566:
1534:
3001:
4962:
4792:
1327:
1405:
233:
197:
418:
4422:
1369:
3710:
3683:
4132:
4083:
R Kumanduri and C Romero, Number Theory w/ Computer
Applications, Alg 9.2.9, Prentice Hall, 1997. A probabilistic for square root of a quadratic residue modulo a prime.
3291:
2122:
2155:
375:
3633:
3332:
3232:
3142:
3031:
2935:
2747:
2667:
2617:
2542:
781:
754:
321:
1809:
1783:
1757:
265:
4550:
1731:
4645:
3601:
3372:
3352:
3252:
3202:
3182:
3162:
3115:
3095:
3071:
3051:
2903:
2880:
2860:
2797:
2771:
2715:
2687:
1558:
1445:
1425:
1240:
1212:
886:
866:
570:
550:
530:
506:
486:
466:
438:
349:
289:
161:
141:
4545:
4274:
3658:
by
Menezes, Oorschot and Vanstone considers this equivalence probable, however, as long as the finding of the roots remains a two-part process (1. roots
3583:
It has been proven that any algorithm which finds one of the possible plaintexts for every Rabin-encrypted ciphertext can be used to factor the modulus
4453:
4447:
1987:
1886:
5010:
4571:
4125:
3955:
3924:
62:
3780:
714:{\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{aligned}}}
2160:
108:
for decryption. The public key is published for anyone to use, while the private key remains known only to the recipient of the message.
4189:
4257:
4214:
4179:
4638:
4065:
4051:
3996:
3851:
4169:
3741:
4118:
4247:
4194:
4333:
3639:
3736:
4841:
4358:
4242:
1814:
3731:
4631:
4499:
4432:
726:
4174:
92:
scheme, which came to be known as the Rabin cryptosystem even though Rabin never published it as an encryption scheme.
19:
This article is about the textbook public-key encryption scheme. For the digital signature scheme it was based on, see
4957:
4912:
4725:
4596:
4489:
4338:
4252:
4237:
3898:
2777:
3477:
2544:
is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate,
4836:
4348:
4219:
1245:
4952:
4601:
4581:
3568:
1685:{\displaystyle m_{p}^{2}\equiv c^{{\frac {1}{2}}(p+1)}\equiv c\cdot c^{{\frac {1}{2}}(p-1)}\equiv c\cdot 1\mod p}
845:
786:
4942:
4932:
4787:
4540:
4311:
3651:
3381:
2802:
1450:
2547:
1496:
2940:
4937:
4927:
4730:
4690:
4683:
4673:
4668:
4494:
4141:
1293:
4678:
4576:
4427:
4366:
4301:
3746:
3721:
3572:
3538:
1374:
202:
166:
3427:
4985:
4831:
4777:
4442:
4199:
4156:
380:
89:
43:
31:
4947:
4871:
4353:
4164:
1696:
1332:
1214:, although which of the four is the correct one cannot be determined without additional information.
4072:
3871:
4710:
4459:
3909:. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416.
4816:
4800:
4747:
4484:
4306:
4229:
4209:
4184:
3688:
3661:
3257:
4876:
4866:
4737:
4566:
4509:
4437:
4323:
4061:
4047:
3992:
3975:
3951:
3920:
3879:(Technical report). Cambridge, MA, United States: MIT Laboratory for Computer Science. TR-212.
3847:
3776:
3542:
3074:
2634:
2091:
1537:
82:
35:
3184:. The expected number of times this algorithm needs to be repeated before finding a suitable
2127:
4811:
4412:
4016:
3910:
3867:
3823:
3800:
3643:
354:
78:
3606:
3305:
3210:
3120:
3009:
2908:
2720:
2640:
2595:
2520:
759:
732:
294:
3894:
3831:
3827:
3561:
2628:
1788:
1762:
1736:
241:
74:
39:
20:
1710:
3983:
4886:
4806:
4767:
4715:
4700:
4020:
3979:
3971:
3906:
3839:
3835:
3804:
3726:
3586:
3357:
3337:
3237:
3187:
3167:
3147:
3100:
3080:
3056:
3036:
2888:
2865:
2845:
2782:
2756:
2700:
2672:
1543:
1430:
1410:
1225:
1197:
871:
851:
555:
535:
515:
491:
471:
451:
423:
334:
274:
146:
126:
5004:
4967:
4922:
4881:
4861:
4757:
4720:
4695:
4012:
3890:
3796:
121:
4917:
4762:
4752:
4742:
4705:
4654:
4606:
4586:
3943:
1222:
We can show that the formulas in step 1 above actually produce the square roots of
4896:
4504:
4381:
3545:
105:
50:
4073:
Digitalized
Signatures and Public-Key Functions as Intractable as Factorization
3873:
Digitalized
Signatures and Public Key Functions as Intractable as Factorization
4856:
4826:
4821:
4782:
4530:
4262:
101:
4019:(July 2008). "§2.3.5 A Squaring Permutation as Hard to Invert as Factoring".
3915:
2078:{\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}
85:
scheme where forging a signature could be proven to be as hard as factoring.
4846:
1977:{\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}
88:
The trapdoor function was later repurposed in textbooks as an example of a
4891:
4851:
4591:
4525:
4396:
4391:
4386:
4267:
3803:(July 2008). "§2.3.4 The Squaring Trapdoor Function Candidate by Rabin".
49:
The Rabin trapdoor function has the advantage that inverting it has been
4417:
4376:
3903:
The Exact
Security of Digital Signatures—How to Sign with RSA and Rabin
3771:
Galbraith, Steven D. (2012). "§24.2: The textbook Rabin cryptosystem".
100:
Like all asymmetric cryptosystems, the Rabin system uses a key pair: a
4772:
4535:
58:
2247:{\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}
4371:
4328:
4296:
4289:
4284:
4279:
4093:
3655:
4627:
4114:
4056:
Menezes, Alfred; van
Oorschot, Paul C.; and Vanstone, Scott A.
73:
The Rabin trapdoor function was first published as part of the
4464:
4318:
116:
The keys for the Rabin cryptosystem are generated as follows:
3693:
3666:
3453:
2567:
2445:
2330:
2060:
2037:
1959:
1936:
1851:
1835:
1517:
1471:
1388:
1307:
1271:
1129:
990:
698:
635:
401:
216:
180:
4076:(in PDF). MIT Laboratory for Computer Science, January 1979.
3950:(3rd ed.). Chapman & Hall/CRC. pp. 211–214.
1242:
as follows. For the first formula, we want to prove that
2633:
The Rabin cryptosystem can be used to create and verify
4793:
Cryptographically secure pseudorandom number generator
3766:
3764:
3762:
3712:
and 2. application of the
Chinese remainder theorem).
1335:
3982:(October 1996). "§8.3: Rabin public-key encryption".
3691:
3664:
3609:
3589:
3564:, which requires the calculation of at least a cube.
3480:
3430:
3384:
3360:
3340:
3308:
3260:
3240:
3213:
3190:
3170:
3150:
3123:
3103:
3083:
3059:
3039:
3012:
2943:
2911:
2891:
2868:
2848:
2805:
2785:
2759:
2723:
2703:
2675:
2643:
2598:
2550:
2523:
2265:
2163:
2130:
2094:
1990:
1889:
1869:{\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}
1817:
1791:
1765:
1739:
1713:
1569:
1546:
1499:
1453:
1433:
1413:
1377:
1296:
1248:
1228:
1200:
896:
874:
854:
789:
762:
735:
580:
558:
538:
518:
494:
474:
454:
426:
383:
357:
337:
297:
277:
244:
205:
169:
149:
129:
4102:
351:
can be encrypted by first converting it to a number
4905:
4661:
4559:
4518:
4477:
4405:
4347:
4228:
4155:
4148:
1194:One of these four values is the original plaintext
3704:
3677:
3627:
3595:
3510:
3464:
3413:
3366:
3346:
3326:
3285:
3246:
3226:
3196:
3176:
3156:
3136:
3109:
3089:
3065:
3045:
3025:
2995:
2929:
2897:
2874:
2854:
2834:
2791:
2765:
2741:
2709:
2681:
2661:
2611:
2584:
2536:
2504:
2246:
2149:
2116:
2077:
1976:
1868:
1803:
1777:
1751:
1725:
1684:
1552:
1528:
1485:
1439:
1419:
1399:
1363:
1321:
1282:
1234:
1206:
1181:
880:
860:
833:
775:
748:
713:
564:
544:
524:
500:
480:
460:
432:
412:
369:
343:
315:
283:
259:
227:
191:
155:
135:
3775:. Cambridge University Press. pp. 491–494.
3560:must be calculated. This is more efficient than
2669:. Verifying a signature requires the public key
2637:. Creating a signature requires the private key
2088:Use the extended Euclidean algorithm to compute
3511:{\displaystyle r'\mathrel {\stackrel {?}{=}} r}
3846:. New York: Academic Press. pp. 155–168.
2842:, where the double-bar denotes concatenation.
4639:
4126:
3650:The Rabin cryptosystem is insecure against a
8:
3575:. Here the efficiency is comparable to RSA.
3401:
2937:. This will produce the usual four results,
2822:
1283:{\displaystyle m_{p}^{2}\equiv c{\bmod {p}}}
3117:. To determine if this is the case, square
834:{\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}
377:using a reversible mapping, then computing
81:. The Rabin signature scheme was the first
4646:
4632:
4624:
4152:
4133:
4119:
4111:
4107:
4103:
4046:. Second Edition. Berlin: Springer, 2001.
3164:, repeat this algorithm with a new random
1811:as our plaintext. The ciphertext is thus
3938:
3936:
3914:
3696:
3692:
3690:
3669:
3665:
3663:
3608:
3588:
3497:
3492:
3490:
3489:
3479:
3456:
3452:
3446:
3429:
3414:{\displaystyle c=H(m\mathbin {\Vert } u)}
3400:
3383:
3359:
3339:
3307:
3268:
3259:
3239:
3218:
3212:
3189:
3169:
3149:
3128:
3122:
3102:
3082:
3058:
3038:
3017:
3011:
2987:
2974:
2961:
2948:
2942:
2910:
2890:
2867:
2847:
2835:{\displaystyle c=H(m\mathbin {\Vert } u)}
2821:
2804:
2784:
2758:
2722:
2702:
2674:
2642:
2603:
2597:
2570:
2566:
2560:
2555:
2549:
2528:
2522:
2470:
2457:
2448:
2444:
2389:
2353:
2333:
2329:
2274:
2266:
2264:
2187:
2168:
2162:
2135:
2129:
2099:
2093:
2063:
2059:
2053:
2040:
2036:
2009:
2008:
1995:
1989:
1962:
1958:
1952:
1939:
1935:
1908:
1907:
1894:
1888:
1854:
1850:
1838:
1834:
1828:
1816:
1790:
1764:
1738:
1712:
1678:
1677:
1634:
1633:
1593:
1592:
1579:
1574:
1568:
1545:
1520:
1516:
1510:
1498:
1486:{\displaystyle c\equiv m^{2}{\bmod {pq}}}
1474:
1470:
1464:
1452:
1432:
1412:
1391:
1387:
1376:
1336:
1334:
1310:
1306:
1295:
1274:
1270:
1258:
1253:
1247:
1227:
1199:
1169:
1146:
1132:
1128:
1117:
1098:
1085:
1066:
1044:
1030:
1007:
993:
989:
978:
959:
946:
927:
905:
897:
895:
873:
853:
813:
794:
788:
767:
761:
740:
734:
701:
697:
670:
669:
652:
638:
634:
607:
606:
589:
581:
579:
557:
537:
517:
493:
473:
453:
425:
404:
400:
394:
382:
356:
336:
296:
276:
243:
219:
215:
204:
183:
179:
168:
148:
128:
3638:The Rabin cryptosystem does not provide
2585:{\displaystyle r_{i}^{2}{\bmod {77}}=15}
1529:{\displaystyle c\equiv m^{2}{\bmod {p}}}
3758:
2996:{\displaystyle r_{1},r_{2},r_{3},r_{4}}
2257:Compute the four plaintext candidates:
1371:is an integer. The proof is trivial if
3907:Advances in Cryptology – EUROCRYPT ’96
3773:Mathematics of Public Key Cryptography
3826:(1978). "Digitalized Signatures". In
3354:can be verified using the public key
3053:. However, this will be true only if
1322:{\displaystyle p\equiv 3{\bmod {4}},}
468:can be recovered from the ciphertext
7:
4454:Naccache–Stern knapsack cryptosystem
4094:Menezes, Oorschot, Vanstone, Scott:
3006:One might expect that squaring each
1400:{\displaystyle c\equiv 0{\bmod {p}}}
228:{\displaystyle q\equiv 3{\bmod {4}}}
192:{\displaystyle p\equiv 3{\bmod {4}}}
4098:(free PDF downloads), see Chapter 8
3465:{\displaystyle r'=c^{2}{\bmod {n}}}
413:{\displaystyle c=m^{2}{\bmod {n}}}
65:that are used widely in practice.
42:, is related to the difficulty of
14:
3948:Cryptography: Theory and Practice
3844:Foundations of Secure Computation
2717:can be signed with a private key
848:to find the four square roots of
488:by taking its square root modulo
4981:
4980:
4096:Handbook of Applied Cryptography
4058:Handbook of Applied Cryptography
3985:Handbook of Applied Cryptography
3656:Handbook of Applied Cryptography
3556:For encryption, a square modulo
2619:encrypts to the same value, 15.
2458:
1879:Decryption proceeds as follows:
1364:{\textstyle {\frac {1}{4}}(p+1)}
4485:Discrete logarithm cryptography
4044:EinfĂĽhrung in die Kryptographie
3991:. CRC Press. pp. 292–294.
2862:should be an integer less than
1673:
291:is the public key and the pair
4842:Information-theoretic security
3622:
3610:
3408:
3394:
3321:
3309:
3280:
3261:
2924:
2912:
2829:
2815:
2736:
2724:
2656:
2644:
2441:
2402:
2326:
2287:
2235:
2223:
2217:
2202:
2031:
2019:
1930:
1918:
1695:The last step is justified by
1656:
1644:
1615:
1603:
1358:
1346:
692:
680:
629:
617:
310:
298:
1:
5011:Public-key encryption schemes
4022:Lecture Notes on Cryptography
3806:Lecture Notes on Cryptography
3548:, eliminating the ambiguity.
38:whose security, like that of
4500:Non-commutative cryptography
3742:Blum–Goldwasser cryptosystem
727:extended Euclidean algorithm
16:Public-key encryption scheme
4958:Message authentication code
4913:Cryptographic hash function
4726:Cryptographic hash function
4597:Identity-based cryptography
4490:Elliptic-curve cryptography
4060:. CRC Press, October 1996.
3705:{\displaystyle {\bmod {q}}}
3678:{\displaystyle {\bmod {p}}}
3571:is applied, along with two
3523:Evaluation of the algorithm
3207:Having found a square root
2778:cryptographic hash function
2623:Digital Signature Algorithm
512:Compute the square root of
5027:
4837:Harvest now, decrypt later
3737:Schmidt–Samoa cryptosystem
3474:The signature is valid if
2626:
120:Choose two large distinct
18:
4976:
4953:Post-quantum cryptography
4623:
4602:Post-quantum cryptography
4551:Post-Quantum Cryptography
4110:
4106:
3569:Chinese remainder theorem
3286:{\displaystyle (r_{1},u)}
3144:. If this does not yield
846:Chinese remainder theorem
4943:Quantum key distribution
4933:Authenticated encryption
4788:Random number generation
3916:10.1007/3-540-68339-9_34
3732:Shanks–Tonelli algorithm
3652:chosen ciphertext attack
3518:and a forgery otherwise.
2753:Generate a random value
2117:{\displaystyle y_{p}=-3}
1407:, so we may assume that
4938:Public-key cryptography
4928:Symmetric-key algorithm
4731:Key derivation function
4691:Cryptographic primitive
4684:Authentication protocol
4674:Outline of cryptography
4669:History of cryptography
4495:Hash-based cryptography
4142:Public-key cryptography
3573:modular exponentiations
2150:{\displaystyle y_{q}=2}
4679:Cryptographic protocol
3722:Topics in cryptography
3706:
3679:
3629:
3597:
3537:structures, or to add
3512:
3466:
3415:
3368:
3348:
3328:
3287:
3248:
3228:
3198:
3178:
3158:
3138:
3111:
3091:
3067:
3047:
3027:
2997:
2931:
2905:using the private key
2899:
2885:Find a square root of
2876:
2856:
2836:
2793:
2767:
2743:
2711:
2683:
2663:
2613:
2586:
2538:
2506:
2248:
2157:. We can confirm that
2151:
2118:
2079:
1978:
1870:
1805:
1779:
1753:
1727:
1686:
1554:
1530:
1487:
1441:
1421:
1401:
1365:
1323:
1284:
1236:
1218:Computing square roots
1208:
1183:
882:
862:
835:
777:
750:
715:
572:using these formulas:
566:
546:
526:
502:
482:
462:
434:
414:
371:
370:{\displaystyle m<n}
345:
317:
285:
261:
229:
193:
157:
137:
4832:End-to-end encryption
4778:Cryptojacking malware
4157:Integer factorization
3976:van Oorschot, Paul C.
3707:
3680:
3630:
3628:{\displaystyle (p,q)}
3598:
3513:
3467:
3416:
3369:
3349:
3329:
3327:{\displaystyle (r,u)}
3298:Verifying a signature
3288:
3249:
3229:
3227:{\displaystyle r_{1}}
3199:
3179:
3159:
3139:
3137:{\displaystyle r_{1}}
3112:
3092:
3068:
3048:
3028:
3026:{\displaystyle r_{i}}
2998:
2932:
2930:{\displaystyle (p,q)}
2900:
2877:
2857:
2837:
2794:
2768:
2744:
2742:{\displaystyle (p,q)}
2712:
2684:
2664:
2662:{\displaystyle (p,q)}
2614:
2612:{\displaystyle r_{i}}
2587:
2539:
2537:{\displaystyle r_{3}}
2507:
2249:
2152:
2119:
2080:
1979:
1871:
1806:
1780:
1754:
1728:
1687:
1555:
1531:
1488:
1442:
1422:
1402:
1366:
1324:
1285:
1237:
1209:
1184:
883:
863:
836:
778:
776:{\displaystyle y_{q}}
751:
749:{\displaystyle y_{p}}
716:
567:
547:
527:
503:
483:
463:
435:
415:
372:
346:
318:
316:{\displaystyle (p,q)}
286:
262:
230:
194:
158:
138:
104:for encryption and a
90:public-key encryption
44:integer factorization
32:public-key encryption
4948:Quantum cryptography
4872:Trusted timestamping
4042:Buchmann, Johannes.
3689:
3662:
3640:indistinguishability
3607:
3587:
3567:For decryption, the
3478:
3428:
3382:
3358:
3338:
3306:
3258:
3238:
3211:
3188:
3168:
3148:
3121:
3101:
3081:
3057:
3037:
3010:
2941:
2909:
2889:
2866:
2846:
2803:
2783:
2757:
2721:
2701:
2673:
2641:
2596:
2548:
2521:
2263:
2161:
2128:
2092:
1988:
1887:
1815:
1804:{\displaystyle m=20}
1789:
1778:{\displaystyle n=77}
1763:
1752:{\displaystyle q=11}
1737:
1711:
1707:As an example, take
1567:
1544:
1497:
1451:
1431:
1411:
1375:
1333:
1294:
1246:
1226:
1198:
894:
872:
852:
787:
760:
733:
578:
556:
536:
516:
492:
472:
452:
424:
420:. The ciphertext is
381:
355:
335:
323:is the private key.
295:
275:
260:{\displaystyle n=pq}
242:
203:
167:
147:
127:
96:Encryption Algorithm
4711:Cryptographic nonce
4460:Three-pass protocol
3828:DeMillo, Richard A.
3747:Kunerth's algorithm
3254:, the signature is
2565:
1726:{\displaystyle p=7}
1584:
1263:
34:schemes based on a
4817:Subliminal channel
4801:Pseudorandom noise
4748:Key (cryptography)
4230:Discrete logarithm
3980:Vanstone, Scott A.
3972:Menezes, Alfred J.
3840:Lipton, Richard J.
3702:
3675:
3625:
3593:
3508:
3462:
3411:
3364:
3344:
3324:
3283:
3244:
3224:
3194:
3174:
3154:
3134:
3107:
3087:
3063:
3043:
3023:
2993:
2927:
2895:
2872:
2852:
2832:
2789:
2763:
2739:
2707:
2679:
2659:
2635:digital signatures
2609:
2582:
2551:
2534:
2502:
2500:
2244:
2147:
2114:
2075:
1974:
1866:
1801:
1775:
1749:
1723:
1682:
1570:
1550:
1526:
1483:
1437:
1417:
1397:
1361:
1319:
1280:
1249:
1232:
1204:
1179:
1177:
878:
858:
831:
773:
746:
711:
709:
562:
542:
522:
498:
478:
458:
430:
410:
367:
341:
313:
281:
257:
225:
189:
153:
133:
77:scheme in 1978 by
28:Rabin cryptosystem
4998:
4997:
4994:
4993:
4877:Key-based routing
4867:Trapdoor function
4738:Digital signature
4619:
4618:
4615:
4614:
4567:Digital signature
4510:Trapdoor function
4473:
4472:
4190:Goldwasser–Micali
4028:. pp. 32–33.
4017:Goldwasser, Shafi
3957:978-1-58488-508-5
3926:978-3-540-61186-8
3868:Rabin, Michael O.
3824:Rabin, Michael O.
3812:. pp. 29–32.
3801:Goldwasser, Shafi
3596:{\displaystyle n}
3502:
3367:{\displaystyle n}
3347:{\displaystyle m}
3247:{\displaystyle c}
3197:{\displaystyle c}
3177:{\displaystyle u}
3157:{\displaystyle c}
3110:{\displaystyle q}
3090:{\displaystyle p}
3075:quadratic residue
3066:{\displaystyle c}
3046:{\displaystyle c}
2898:{\displaystyle c}
2875:{\displaystyle n}
2855:{\displaystyle c}
2792:{\displaystyle H}
2766:{\displaystyle u}
2710:{\displaystyle m}
2682:{\displaystyle n}
2017:
1916:
1697:Euler's criterion
1642:
1601:
1553:{\displaystyle p}
1538:quadratic residue
1440:{\displaystyle c}
1420:{\displaystyle p}
1344:
1235:{\displaystyle c}
1207:{\displaystyle m}
881:{\displaystyle n}
861:{\displaystyle c}
678:
615:
565:{\displaystyle q}
545:{\displaystyle p}
525:{\displaystyle c}
501:{\displaystyle n}
481:{\displaystyle c}
461:{\displaystyle m}
433:{\displaystyle c}
344:{\displaystyle M}
284:{\displaystyle n}
156:{\displaystyle q}
136:{\displaystyle p}
83:digital signature
36:trapdoor function
5018:
4984:
4983:
4812:Insecure channel
4648:
4641:
4634:
4625:
4456:
4357:
4352:
4312:signature scheme
4215:Okamoto–Uchiyama
4153:
4135:
4128:
4121:
4112:
4108:
4104:
4070:Rabin, Michael.
4030:
4029:
4027:
4009:
4003:
4002:
3990:
3968:
3962:
3961:
3944:Stinson, Douglas
3940:
3931:
3930:
3918:
3895:Rogaway, Phillip
3887:
3881:
3880:
3878:
3870:(January 1979).
3864:
3858:
3857:
3832:Dobkin, David P.
3820:
3814:
3813:
3811:
3793:
3787:
3786:
3782:978-1-10701392-6
3768:
3711:
3709:
3708:
3703:
3701:
3700:
3684:
3682:
3681:
3676:
3674:
3673:
3644:chosen plaintext
3634:
3632:
3631:
3626:
3602:
3600:
3599:
3594:
3517:
3515:
3514:
3509:
3504:
3503:
3501:
3496:
3491:
3488:
3471:
3469:
3468:
3463:
3461:
3460:
3451:
3450:
3438:
3420:
3418:
3417:
3412:
3404:
3373:
3371:
3370:
3365:
3353:
3351:
3350:
3345:
3333:
3331:
3330:
3325:
3292:
3290:
3289:
3284:
3273:
3272:
3253:
3251:
3250:
3245:
3233:
3231:
3230:
3225:
3223:
3222:
3203:
3201:
3200:
3195:
3183:
3181:
3180:
3175:
3163:
3161:
3160:
3155:
3143:
3141:
3140:
3135:
3133:
3132:
3116:
3114:
3113:
3108:
3096:
3094:
3093:
3088:
3073:happens to be a
3072:
3070:
3069:
3064:
3052:
3050:
3049:
3044:
3032:
3030:
3029:
3024:
3022:
3021:
3002:
3000:
2999:
2994:
2992:
2991:
2979:
2978:
2966:
2965:
2953:
2952:
2936:
2934:
2933:
2928:
2904:
2902:
2901:
2896:
2881:
2879:
2878:
2873:
2861:
2859:
2858:
2853:
2841:
2839:
2838:
2833:
2825:
2798:
2796:
2795:
2790:
2772:
2770:
2769:
2764:
2748:
2746:
2745:
2740:
2716:
2714:
2713:
2708:
2688:
2686:
2685:
2680:
2668:
2666:
2665:
2660:
2618:
2616:
2615:
2610:
2608:
2607:
2591:
2589:
2588:
2583:
2575:
2574:
2564:
2559:
2543:
2541:
2540:
2535:
2533:
2532:
2517:and we see that
2511:
2509:
2508:
2503:
2501:
2475:
2474:
2461:
2453:
2452:
2394:
2393:
2358:
2357:
2338:
2337:
2279:
2278:
2253:
2251:
2250:
2245:
2192:
2191:
2173:
2172:
2156:
2154:
2153:
2148:
2140:
2139:
2123:
2121:
2120:
2115:
2104:
2103:
2084:
2082:
2081:
2076:
2068:
2067:
2058:
2057:
2045:
2044:
2035:
2034:
2018:
2010:
2000:
1999:
1983:
1981:
1980:
1975:
1967:
1966:
1957:
1956:
1944:
1943:
1934:
1933:
1917:
1909:
1899:
1898:
1875:
1873:
1872:
1867:
1859:
1858:
1843:
1842:
1833:
1832:
1810:
1808:
1807:
1802:
1784:
1782:
1781:
1776:
1758:
1756:
1755:
1750:
1732:
1730:
1729:
1724:
1691:
1689:
1688:
1683:
1660:
1659:
1643:
1635:
1619:
1618:
1602:
1594:
1583:
1578:
1559:
1557:
1556:
1551:
1535:
1533:
1532:
1527:
1525:
1524:
1515:
1514:
1492:
1490:
1489:
1484:
1482:
1481:
1469:
1468:
1446:
1444:
1443:
1438:
1427:does not divide
1426:
1424:
1423:
1418:
1406:
1404:
1403:
1398:
1396:
1395:
1370:
1368:
1367:
1362:
1345:
1337:
1328:
1326:
1325:
1320:
1315:
1314:
1289:
1287:
1286:
1281:
1279:
1278:
1262:
1257:
1241:
1239:
1238:
1233:
1213:
1211:
1210:
1205:
1188:
1186:
1185:
1180:
1178:
1174:
1173:
1151:
1150:
1137:
1136:
1127:
1123:
1122:
1121:
1103:
1102:
1090:
1089:
1071:
1070:
1049:
1048:
1035:
1034:
1012:
1011:
998:
997:
988:
984:
983:
982:
964:
963:
951:
950:
932:
931:
910:
909:
887:
885:
884:
879:
867:
865:
864:
859:
840:
838:
837:
832:
818:
817:
799:
798:
782:
780:
779:
774:
772:
771:
755:
753:
752:
747:
745:
744:
720:
718:
717:
712:
710:
706:
705:
696:
695:
679:
671:
657:
656:
643:
642:
633:
632:
616:
608:
594:
593:
571:
569:
568:
563:
551:
549:
548:
543:
531:
529:
528:
523:
507:
505:
504:
499:
487:
485:
484:
479:
467:
465:
464:
459:
439:
437:
436:
431:
419:
417:
416:
411:
409:
408:
399:
398:
376:
374:
373:
368:
350:
348:
347:
342:
322:
320:
319:
314:
290:
288:
287:
282:
266:
264:
263:
258:
234:
232:
231:
226:
224:
223:
198:
196:
195:
190:
188:
187:
162:
160:
159:
154:
142:
140:
139:
134:
79:Michael O. Rabin
59:RSAES-PKCS1-v1_5
5026:
5025:
5021:
5020:
5019:
5017:
5016:
5015:
5001:
5000:
4999:
4990:
4972:
4901:
4657:
4652:
4611:
4555:
4519:Standardization
4514:
4469:
4452:
4401:
4349:Lattice/SVP/CVP
4343:
4224:
4170:Blum–Goldwasser
4144:
4139:
4090:
4039:
4034:
4033:
4025:
4011:
4010:
4006:
3999:
3988:
3970:
3969:
3965:
3958:
3946:(2006). "5.8".
3942:
3941:
3934:
3927:
3889:
3888:
3884:
3876:
3866:
3865:
3861:
3854:
3836:Jones, Anita K.
3822:
3821:
3817:
3809:
3795:
3794:
3790:
3783:
3770:
3769:
3760:
3755:
3718:
3687:
3686:
3660:
3659:
3605:
3604:
3585:
3584:
3581:
3554:
3530:
3525:
3481:
3476:
3475:
3442:
3431:
3426:
3425:
3380:
3379:
3356:
3355:
3336:
3335:
3304:
3303:
3300:
3264:
3256:
3255:
3236:
3235:
3214:
3209:
3208:
3186:
3185:
3166:
3165:
3146:
3145:
3124:
3119:
3118:
3099:
3098:
3079:
3078:
3055:
3054:
3035:
3034:
3013:
3008:
3007:
2983:
2970:
2957:
2944:
2939:
2938:
2907:
2906:
2887:
2886:
2864:
2863:
2844:
2843:
2801:
2800:
2781:
2780:
2755:
2754:
2719:
2718:
2699:
2698:
2695:
2671:
2670:
2639:
2638:
2631:
2629:Rabin signature
2625:
2599:
2594:
2593:
2546:
2545:
2524:
2519:
2518:
2499:
2498:
2476:
2466:
2463:
2462:
2395:
2385:
2382:
2381:
2359:
2349:
2346:
2345:
2280:
2270:
2261:
2260:
2183:
2164:
2159:
2158:
2131:
2126:
2125:
2095:
2090:
2089:
2049:
2004:
1991:
1986:
1985:
1948:
1903:
1890:
1885:
1884:
1824:
1813:
1812:
1787:
1786:
1761:
1760:
1735:
1734:
1709:
1708:
1705:
1629:
1588:
1565:
1564:
1542:
1541:
1506:
1495:
1494:
1460:
1449:
1448:
1429:
1428:
1409:
1408:
1373:
1372:
1331:
1330:
1292:
1291:
1244:
1243:
1224:
1223:
1220:
1196:
1195:
1176:
1175:
1165:
1152:
1142:
1139:
1138:
1113:
1094:
1081:
1062:
1061:
1057:
1050:
1040:
1037:
1036:
1026:
1013:
1003:
1000:
999:
974:
955:
942:
923:
922:
918:
911:
901:
892:
891:
870:
869:
850:
849:
809:
790:
785:
784:
763:
758:
757:
736:
731:
730:
708:
707:
665:
658:
648:
645:
644:
602:
595:
585:
576:
575:
554:
553:
534:
533:
514:
513:
490:
489:
470:
469:
450:
449:
446:
422:
421:
390:
379:
378:
353:
352:
333:
332:
329:
293:
292:
273:
272:
240:
239:
201:
200:
165:
164:
145:
144:
125:
124:
114:
98:
75:Rabin signature
71:
30:is a family of
24:
21:Rabin signature
17:
12:
11:
5:
5024:
5022:
5014:
5013:
5003:
5002:
4996:
4995:
4992:
4991:
4989:
4988:
4977:
4974:
4973:
4971:
4970:
4965:
4963:Random numbers
4960:
4955:
4950:
4945:
4940:
4935:
4930:
4925:
4920:
4915:
4909:
4907:
4903:
4902:
4900:
4899:
4894:
4889:
4887:Garlic routing
4884:
4879:
4874:
4869:
4864:
4859:
4854:
4849:
4844:
4839:
4834:
4829:
4824:
4819:
4814:
4809:
4807:Secure channel
4804:
4798:
4797:
4796:
4785:
4780:
4775:
4770:
4768:Key stretching
4765:
4760:
4755:
4750:
4745:
4740:
4735:
4734:
4733:
4728:
4718:
4716:Cryptovirology
4713:
4708:
4703:
4701:Cryptocurrency
4698:
4693:
4688:
4687:
4686:
4676:
4671:
4665:
4663:
4659:
4658:
4653:
4651:
4650:
4643:
4636:
4628:
4621:
4620:
4617:
4616:
4613:
4612:
4610:
4609:
4604:
4599:
4594:
4589:
4584:
4579:
4574:
4569:
4563:
4561:
4557:
4556:
4554:
4553:
4548:
4543:
4538:
4533:
4528:
4522:
4520:
4516:
4515:
4513:
4512:
4507:
4502:
4497:
4492:
4487:
4481:
4479:
4475:
4474:
4471:
4470:
4468:
4467:
4462:
4457:
4450:
4448:Merkle–Hellman
4445:
4440:
4435:
4430:
4425:
4420:
4415:
4409:
4407:
4403:
4402:
4400:
4399:
4394:
4389:
4384:
4379:
4374:
4369:
4363:
4361:
4345:
4344:
4342:
4341:
4336:
4331:
4326:
4321:
4316:
4315:
4314:
4304:
4299:
4294:
4293:
4292:
4287:
4277:
4272:
4271:
4270:
4265:
4255:
4250:
4245:
4240:
4234:
4232:
4226:
4225:
4223:
4222:
4217:
4212:
4207:
4202:
4197:
4195:Naccache–Stern
4192:
4187:
4182:
4177:
4172:
4167:
4161:
4159:
4150:
4146:
4145:
4140:
4138:
4137:
4130:
4123:
4115:
4101:
4100:
4089:
4088:External links
4086:
4085:
4084:
4081:
4077:
4068:
4054:
4038:
4035:
4032:
4031:
4013:Bellare, Mihir
4004:
3997:
3963:
3956:
3932:
3925:
3891:Bellare, Mihir
3882:
3859:
3852:
3815:
3797:Bellare, Mihir
3788:
3781:
3757:
3756:
3754:
3751:
3750:
3749:
3744:
3739:
3734:
3729:
3727:Blum Blum Shub
3724:
3717:
3714:
3699:
3695:
3672:
3668:
3624:
3621:
3618:
3615:
3612:
3592:
3580:
3577:
3553:
3550:
3529:
3526:
3524:
3521:
3520:
3519:
3507:
3500:
3495:
3487:
3484:
3472:
3459:
3455:
3449:
3445:
3441:
3437:
3434:
3422:
3410:
3407:
3403:
3399:
3396:
3393:
3390:
3387:
3363:
3343:
3334:for a message
3323:
3320:
3317:
3314:
3311:
3299:
3296:
3295:
3294:
3282:
3279:
3276:
3271:
3267:
3263:
3243:
3221:
3217:
3205:
3193:
3173:
3153:
3131:
3127:
3106:
3086:
3062:
3042:
3033:would produce
3020:
3016:
3004:
2990:
2986:
2982:
2977:
2973:
2969:
2964:
2960:
2956:
2951:
2947:
2926:
2923:
2920:
2917:
2914:
2894:
2883:
2871:
2851:
2831:
2828:
2824:
2820:
2817:
2814:
2811:
2808:
2788:
2774:
2762:
2738:
2735:
2732:
2729:
2726:
2706:
2694:
2691:
2678:
2658:
2655:
2652:
2649:
2646:
2627:Main article:
2624:
2621:
2606:
2602:
2581:
2578:
2573:
2569:
2563:
2558:
2554:
2531:
2527:
2515:
2514:
2513:
2512:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2477:
2473:
2469:
2465:
2464:
2460:
2456:
2451:
2447:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2396:
2392:
2388:
2384:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2360:
2356:
2352:
2348:
2347:
2344:
2341:
2336:
2332:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2281:
2277:
2273:
2269:
2268:
2255:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2190:
2186:
2182:
2179:
2176:
2171:
2167:
2146:
2143:
2138:
2134:
2113:
2110:
2107:
2102:
2098:
2086:
2074:
2071:
2066:
2062:
2056:
2052:
2048:
2043:
2039:
2033:
2030:
2027:
2024:
2021:
2016:
2013:
2007:
2003:
1998:
1994:
1973:
1970:
1965:
1961:
1955:
1951:
1947:
1942:
1938:
1932:
1929:
1926:
1923:
1920:
1915:
1912:
1906:
1902:
1897:
1893:
1865:
1862:
1857:
1853:
1849:
1846:
1841:
1837:
1831:
1827:
1823:
1820:
1800:
1797:
1794:
1774:
1771:
1768:
1748:
1745:
1742:
1722:
1719:
1716:
1704:
1701:
1693:
1692:
1681:
1676:
1672:
1669:
1666:
1663:
1658:
1655:
1652:
1649:
1646:
1641:
1638:
1632:
1628:
1625:
1622:
1617:
1614:
1611:
1608:
1605:
1600:
1597:
1591:
1587:
1582:
1577:
1573:
1549:
1523:
1519:
1513:
1509:
1505:
1502:
1480:
1477:
1473:
1467:
1463:
1459:
1456:
1436:
1416:
1394:
1390:
1386:
1383:
1380:
1360:
1357:
1354:
1351:
1348:
1343:
1340:
1318:
1313:
1309:
1305:
1302:
1299:
1277:
1273:
1269:
1266:
1261:
1256:
1252:
1231:
1219:
1216:
1203:
1192:
1191:
1190:
1189:
1172:
1168:
1164:
1161:
1158:
1155:
1153:
1149:
1145:
1141:
1140:
1135:
1131:
1126:
1120:
1116:
1112:
1109:
1106:
1101:
1097:
1093:
1088:
1084:
1080:
1077:
1074:
1069:
1065:
1060:
1056:
1053:
1051:
1047:
1043:
1039:
1038:
1033:
1029:
1025:
1022:
1019:
1016:
1014:
1010:
1006:
1002:
1001:
996:
992:
987:
981:
977:
973:
970:
967:
962:
958:
954:
949:
945:
941:
938:
935:
930:
926:
921:
917:
914:
912:
908:
904:
900:
899:
877:
857:
842:
830:
827:
824:
821:
816:
812:
808:
805:
802:
797:
793:
770:
766:
743:
739:
723:
722:
721:
704:
700:
694:
691:
688:
685:
682:
677:
674:
668:
664:
661:
659:
655:
651:
647:
646:
641:
637:
631:
628:
625:
622:
619:
614:
611:
605:
601:
598:
596:
592:
588:
584:
583:
561:
541:
521:
497:
477:
457:
445:
442:
429:
407:
403:
397:
393:
389:
386:
366:
363:
360:
340:
328:
325:
312:
309:
306:
303:
300:
280:
269:
268:
256:
253:
250:
247:
236:
222:
218:
214:
211:
208:
186:
182:
178:
175:
172:
152:
132:
113:
112:Key generation
110:
97:
94:
70:
67:
51:mathematically
15:
13:
10:
9:
6:
4:
3:
2:
5023:
5012:
5009:
5008:
5006:
4987:
4979:
4978:
4975:
4969:
4968:Steganography
4966:
4964:
4961:
4959:
4956:
4954:
4951:
4949:
4946:
4944:
4941:
4939:
4936:
4934:
4931:
4929:
4926:
4924:
4923:Stream cipher
4921:
4919:
4916:
4914:
4911:
4910:
4908:
4904:
4898:
4895:
4893:
4890:
4888:
4885:
4883:
4882:Onion routing
4880:
4878:
4875:
4873:
4870:
4868:
4865:
4863:
4862:Shared secret
4860:
4858:
4855:
4853:
4850:
4848:
4845:
4843:
4840:
4838:
4835:
4833:
4830:
4828:
4825:
4823:
4820:
4818:
4815:
4813:
4810:
4808:
4805:
4802:
4799:
4794:
4791:
4790:
4789:
4786:
4784:
4781:
4779:
4776:
4774:
4771:
4769:
4766:
4764:
4761:
4759:
4758:Key generator
4756:
4754:
4751:
4749:
4746:
4744:
4741:
4739:
4736:
4732:
4729:
4727:
4724:
4723:
4722:
4721:Hash function
4719:
4717:
4714:
4712:
4709:
4707:
4704:
4702:
4699:
4697:
4696:Cryptanalysis
4694:
4692:
4689:
4685:
4682:
4681:
4680:
4677:
4675:
4672:
4670:
4667:
4666:
4664:
4660:
4656:
4649:
4644:
4642:
4637:
4635:
4630:
4629:
4626:
4622:
4608:
4605:
4603:
4600:
4598:
4595:
4593:
4590:
4588:
4585:
4583:
4580:
4578:
4575:
4573:
4570:
4568:
4565:
4564:
4562:
4558:
4552:
4549:
4547:
4544:
4542:
4539:
4537:
4534:
4532:
4529:
4527:
4524:
4523:
4521:
4517:
4511:
4508:
4506:
4503:
4501:
4498:
4496:
4493:
4491:
4488:
4486:
4483:
4482:
4480:
4476:
4466:
4463:
4461:
4458:
4455:
4451:
4449:
4446:
4444:
4441:
4439:
4436:
4434:
4431:
4429:
4426:
4424:
4421:
4419:
4416:
4414:
4411:
4410:
4408:
4404:
4398:
4395:
4393:
4390:
4388:
4385:
4383:
4380:
4378:
4375:
4373:
4370:
4368:
4365:
4364:
4362:
4360:
4355:
4350:
4346:
4340:
4337:
4335:
4332:
4330:
4327:
4325:
4322:
4320:
4317:
4313:
4310:
4309:
4308:
4305:
4303:
4300:
4298:
4295:
4291:
4288:
4286:
4283:
4282:
4281:
4278:
4276:
4273:
4269:
4266:
4264:
4261:
4260:
4259:
4256:
4254:
4251:
4249:
4246:
4244:
4241:
4239:
4236:
4235:
4233:
4231:
4227:
4221:
4220:Schmidt–Samoa
4218:
4216:
4213:
4211:
4208:
4206:
4203:
4201:
4198:
4196:
4193:
4191:
4188:
4186:
4183:
4181:
4180:Damgård–Jurik
4178:
4176:
4175:Cayley–Purser
4173:
4171:
4168:
4166:
4163:
4162:
4160:
4158:
4154:
4151:
4147:
4143:
4136:
4131:
4129:
4124:
4122:
4117:
4116:
4113:
4109:
4105:
4099:
4097:
4092:
4091:
4087:
4082:
4078:
4075:
4074:
4069:
4067:
4066:0-8493-8523-7
4063:
4059:
4055:
4053:
4052:3-540-41283-2
4049:
4045:
4041:
4040:
4036:
4024:
4023:
4018:
4014:
4008:
4005:
4000:
3998:0-8493-8523-7
3994:
3987:
3986:
3981:
3977:
3973:
3967:
3964:
3959:
3953:
3949:
3945:
3939:
3937:
3933:
3928:
3922:
3917:
3912:
3908:
3904:
3900:
3896:
3892:
3886:
3883:
3875:
3874:
3869:
3863:
3860:
3855:
3853:0-12-210350-5
3849:
3845:
3841:
3837:
3833:
3829:
3825:
3819:
3816:
3808:
3807:
3802:
3798:
3792:
3789:
3784:
3778:
3774:
3767:
3765:
3763:
3759:
3752:
3748:
3745:
3743:
3740:
3738:
3735:
3733:
3730:
3728:
3725:
3723:
3720:
3719:
3715:
3713:
3697:
3670:
3657:
3653:
3648:
3645:
3641:
3636:
3619:
3616:
3613:
3590:
3578:
3576:
3574:
3570:
3565:
3563:
3559:
3551:
3549:
3547:
3544:
3540:
3534:
3528:Effectiveness
3527:
3522:
3505:
3498:
3493:
3485:
3482:
3473:
3457:
3447:
3443:
3439:
3435:
3432:
3423:
3405:
3397:
3391:
3388:
3385:
3377:
3376:
3375:
3361:
3341:
3318:
3315:
3312:
3297:
3277:
3274:
3269:
3265:
3241:
3219:
3215:
3206:
3191:
3171:
3151:
3129:
3125:
3104:
3084:
3076:
3060:
3040:
3018:
3014:
3005:
2988:
2984:
2980:
2975:
2971:
2967:
2962:
2958:
2954:
2949:
2945:
2921:
2918:
2915:
2892:
2884:
2869:
2849:
2826:
2818:
2812:
2809:
2806:
2786:
2779:
2775:
2760:
2752:
2751:
2750:
2733:
2730:
2727:
2704:
2692:
2690:
2676:
2653:
2650:
2647:
2636:
2630:
2622:
2620:
2604:
2600:
2579:
2576:
2571:
2561:
2556:
2552:
2529:
2525:
2495:
2492:
2489:
2486:
2483:
2480:
2478:
2471:
2467:
2454:
2449:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2399:
2397:
2390:
2386:
2378:
2375:
2372:
2369:
2366:
2363:
2361:
2354:
2350:
2342:
2339:
2334:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2284:
2282:
2275:
2271:
2259:
2258:
2256:
2241:
2238:
2232:
2229:
2226:
2220:
2214:
2211:
2208:
2205:
2199:
2196:
2193:
2188:
2184:
2180:
2177:
2174:
2169:
2165:
2144:
2141:
2136:
2132:
2111:
2108:
2105:
2100:
2096:
2087:
2072:
2069:
2064:
2054:
2050:
2046:
2041:
2028:
2025:
2022:
2014:
2011:
2005:
2001:
1996:
1992:
1971:
1968:
1963:
1953:
1949:
1945:
1940:
1927:
1924:
1921:
1913:
1910:
1904:
1900:
1895:
1891:
1882:
1881:
1880:
1877:
1863:
1860:
1855:
1847:
1844:
1839:
1829:
1825:
1821:
1818:
1798:
1795:
1792:
1772:
1769:
1766:
1746:
1743:
1740:
1720:
1717:
1714:
1702:
1700:
1698:
1679:
1674:
1670:
1667:
1664:
1661:
1653:
1650:
1647:
1639:
1636:
1630:
1626:
1623:
1620:
1612:
1609:
1606:
1598:
1595:
1589:
1585:
1580:
1575:
1571:
1563:
1562:
1561:
1547:
1539:
1521:
1511:
1507:
1503:
1500:
1493:implies that
1478:
1475:
1465:
1461:
1457:
1454:
1434:
1414:
1392:
1384:
1381:
1378:
1355:
1352:
1349:
1341:
1338:
1329:the exponent
1316:
1311:
1303:
1300:
1297:
1275:
1267:
1264:
1259:
1254:
1250:
1229:
1217:
1215:
1201:
1170:
1166:
1162:
1159:
1156:
1154:
1147:
1143:
1133:
1124:
1118:
1114:
1110:
1107:
1104:
1099:
1095:
1091:
1086:
1082:
1078:
1075:
1072:
1067:
1063:
1058:
1054:
1052:
1045:
1041:
1031:
1027:
1023:
1020:
1017:
1015:
1008:
1004:
994:
985:
979:
975:
971:
968:
965:
960:
956:
952:
947:
943:
939:
936:
933:
928:
924:
919:
915:
913:
906:
902:
890:
889:
875:
855:
847:
843:
828:
825:
822:
819:
814:
810:
806:
803:
800:
795:
791:
768:
764:
741:
737:
728:
724:
702:
689:
686:
683:
675:
672:
666:
662:
660:
653:
649:
639:
626:
623:
620:
612:
609:
603:
599:
597:
590:
586:
574:
573:
559:
539:
519:
511:
510:
509:
495:
475:
455:
443:
441:
427:
405:
395:
391:
387:
384:
364:
361:
358:
338:
326:
324:
307:
304:
301:
278:
254:
251:
248:
245:
237:
220:
212:
209:
206:
184:
176:
173:
170:
150:
130:
123:
122:prime numbers
119:
118:
117:
111:
109:
107:
103:
95:
93:
91:
86:
84:
80:
76:
68:
66:
64:
60:
55:
52:
47:
45:
41:
37:
33:
29:
22:
4918:Block cipher
4763:Key schedule
4753:Key exchange
4743:Kleptography
4706:Cryptosystem
4655:Cryptography
4607:OpenPGP card
4587:Web of trust
4243:Cramer–Shoup
4204:
4095:
4071:
4057:
4043:
4021:
4007:
3984:
3966:
3947:
3902:
3899:Maurer, Ueli
3897:(May 1996).
3885:
3872:
3862:
3843:
3818:
3805:
3791:
3772:
3649:
3637:
3582:
3566:
3557:
3555:
3535:
3531:
3374:as follows.
3302:A signature
3301:
2749:as follows.
2696:
2632:
2516:
1878:
1706:
1694:
1536:, so c is a
1447:. Note that
1221:
1193:
508:as follows.
448:The message
447:
330:
270:
115:
99:
87:
72:
56:
48:
27:
25:
4906:Mathematics
4897:Mix network
4577:Fingerprint
4541:NSA Suite B
4505:RSA problem
4382:NTRUEncrypt
3546:permutation
2799:to compute
106:private key
4857:Ciphertext
4827:Decryption
4822:Encryption
4783:Ransomware
4531:IEEE P1363
4149:Algorithms
4037:References
3552:Efficiency
2697:A message
2592:, so each
783:such that
444:Decryption
331:A message
327:Encryption
163:such that
102:public key
63:RSAES-OAEP
4847:Plaintext
3402:‖
2823:‖
2487:−
2436:⋅
2430:⋅
2424:−
2418:⋅
2412:⋅
2406:−
2370:−
2321:⋅
2315:⋅
2303:⋅
2297:⋅
2291:−
2230:⋅
2212:⋅
2206:−
2194:⋅
2175:⋅
2109:−
1668:⋅
1662:≡
1651:−
1627:⋅
1621:≡
1586:≡
1504:≡
1458:≡
1382:≡
1301:≡
1265:≡
1163:−
1111:⋅
1105:⋅
1092:−
1079:⋅
1073:⋅
1024:−
972:⋅
966:⋅
940:⋅
934:⋅
820:⋅
801:⋅
210:≡
174:≡
5005:Category
4986:Category
4892:Kademlia
4852:Codetext
4795:(CSPRNG)
4592:Key size
4526:CRYPTREC
4443:McEliece
4397:RLWE-SIG
4392:RLWE-KEX
4387:NTRUSign
4200:Paillier
3842:(eds.).
3716:See also
3642:against
3579:Security
3543:trapdoor
3486:′
3436:′
3424:Compute
3378:Compute
1883:Compute
1290:. Since
844:Use the
729:to find
725:Use the
238:Compute
4662:General
4438:Lamport
4418:CEILIDH
4377:NewHope
4324:Schnorr
4307:ElGamal
4285:Ed25519
4165:Benaloh
3901:(ed.).
3539:padding
3077:modulo
2693:Signing
1785:. Take
1759:, then
1703:Example
1560:. Then
1540:modulo
868:modulo
532:modulo
69:History
4773:Keygen
4560:Topics
4536:NESSIE
4478:Theory
4406:Others
4263:X25519
4064:
4050:
3995:
3954:
3923:
3850:
3779:
2776:Use a
4803:(PRN)
4372:Kyber
4367:BLISS
4329:SPEKE
4297:ECMQV
4290:Ed448
4280:EdDSA
4275:ECDSA
4205:Rabin
4080:1999.
4026:(PDF)
3989:(PDF)
3877:(PDF)
3810:(PDF)
3753:Notes
3204:is 4.
271:Then
4572:OAEP
4546:CNSA
4423:EPOC
4268:X448
4258:ECDH
4062:ISBN
4048:ISBN
3993:ISBN
3952:ISBN
3921:ISBN
3848:ISBN
3777:ISBN
3685:and
3097:and
2124:and
1984:and
1733:and
756:and
552:and
362:<
199:and
143:and
61:and
26:The
4582:PKI
4465:XTR
4433:IES
4428:HFE
4359:SIS
4354:LWE
4339:STS
4334:SRP
4319:MQV
4302:EKE
4253:DSA
4238:BLS
4210:RSA
4185:GMR
3911:doi
3694:mod
3667:mod
3562:RSA
3454:mod
3234:of
2568:mod
2446:mod
2331:mod
2061:mod
2038:mod
1960:mod
1937:mod
1852:mod
1848:400
1836:mod
1675:mod
1518:mod
1472:mod
1389:mod
1308:mod
1272:mod
1130:mod
991:mod
699:mod
636:mod
402:mod
217:mod
181:mod
40:RSA
5007::
4413:AE
4248:DH
4015:;
3978:;
3974:;
3935:^
3919:.
3905:.
3893:;
3838:;
3834:;
3830:;
3799:;
3761:^
3635:.
2689:.
2580:15
2572:77
2496:57
2490:20
2484:77
2459:20
2450:77
2433:11
2379:13
2373:64
2367:77
2343:64
2335:77
2318:11
2233:11
2065:11
2051:15
1950:15
1876:.
1864:15
1856:77
1799:20
1773:77
1747:11
1699:.
888::
440:.
46:.
4647:e
4640:t
4633:v
4356:/
4351:/
4134:e
4127:t
4120:v
4001:.
3960:.
3929:.
3913::
3856:.
3785:.
3698:q
3671:p
3623:)
3620:q
3617:,
3614:p
3611:(
3591:n
3558:n
3506:r
3499:?
3494:=
3483:r
3458:n
3448:2
3444:c
3440:=
3433:r
3421:.
3409:)
3406:u
3398:m
3395:(
3392:H
3389:=
3386:c
3362:n
3342:m
3322:)
3319:u
3316:,
3313:r
3310:(
3293:.
3281:)
3278:u
3275:,
3270:1
3266:r
3262:(
3242:c
3220:1
3216:r
3192:c
3172:u
3152:c
3130:1
3126:r
3105:q
3085:p
3061:c
3041:c
3019:i
3015:r
3003:.
2989:4
2985:r
2981:,
2976:3
2972:r
2968:,
2963:2
2959:r
2955:,
2950:1
2946:r
2925:)
2922:q
2919:,
2916:p
2913:(
2893:c
2882:.
2870:n
2850:c
2830:)
2827:u
2819:m
2816:(
2813:H
2810:=
2807:c
2787:H
2773:.
2761:u
2737:)
2734:q
2731:,
2728:p
2725:(
2705:m
2677:n
2657:)
2654:q
2651:,
2648:p
2645:(
2605:i
2601:r
2577:=
2562:2
2557:i
2553:r
2530:3
2526:r
2493:=
2481:=
2472:4
2468:r
2455:=
2442:)
2439:1
2427:2
2421:9
2415:7
2409:3
2403:(
2400:=
2391:3
2387:r
2376:=
2364:=
2355:2
2351:r
2340:=
2327:)
2324:1
2312:2
2309:+
2306:9
2300:7
2294:3
2288:(
2285:=
2276:1
2272:r
2254:.
2242:1
2239:=
2236:)
2227:2
2224:(
2221:+
2218:)
2215:7
2209:3
2203:(
2200:=
2197:q
2189:q
2185:y
2181:+
2178:p
2170:p
2166:y
2145:2
2142:=
2137:q
2133:y
2112:3
2106:=
2101:p
2097:y
2085:.
2073:9
2070:=
2055:3
2047:=
2042:q
2032:)
2029:1
2026:+
2023:q
2020:(
2015:4
2012:1
2006:c
2002:=
1997:q
1993:m
1972:1
1969:=
1964:7
1954:2
1946:=
1941:p
1931:)
1928:1
1925:+
1922:p
1919:(
1914:4
1911:1
1905:c
1901:=
1896:p
1892:m
1861:=
1845:=
1840:n
1830:2
1826:m
1822:=
1819:c
1796:=
1793:m
1770:=
1767:n
1744:=
1741:q
1721:7
1718:=
1715:p
1680:p
1671:1
1665:c
1657:)
1654:1
1648:p
1645:(
1640:2
1637:1
1631:c
1624:c
1616:)
1613:1
1610:+
1607:p
1604:(
1599:2
1596:1
1590:c
1581:2
1576:p
1572:m
1548:p
1522:p
1512:2
1508:m
1501:c
1479:q
1476:p
1466:2
1462:m
1455:c
1435:c
1415:p
1393:p
1385:0
1379:c
1359:)
1356:1
1353:+
1350:p
1347:(
1342:4
1339:1
1317:,
1312:4
1304:3
1298:p
1276:p
1268:c
1260:2
1255:p
1251:m
1230:c
1202:m
1171:3
1167:r
1160:n
1157:=
1148:4
1144:r
1134:n
1125:)
1119:p
1115:m
1108:q
1100:q
1096:y
1087:q
1083:m
1076:p
1068:p
1064:y
1059:(
1055:=
1046:3
1042:r
1032:1
1028:r
1021:n
1018:=
1009:2
1005:r
995:n
986:)
980:p
976:m
969:q
961:q
957:y
953:+
948:q
944:m
937:p
929:p
925:y
920:(
916:=
907:1
903:r
876:n
856:c
841:.
829:1
826:=
823:q
815:q
811:y
807:+
804:p
796:p
792:y
769:q
765:y
742:p
738:y
703:q
693:)
690:1
687:+
684:q
681:(
676:4
673:1
667:c
663:=
654:q
650:m
640:p
630:)
627:1
624:+
621:p
618:(
613:4
610:1
604:c
600:=
591:p
587:m
560:q
540:p
520:c
496:n
476:c
456:m
428:c
406:n
396:2
392:m
388:=
385:c
365:n
359:m
339:M
311:)
308:q
305:,
302:p
299:(
279:n
267:.
255:q
252:p
249:=
246:n
235:.
221:4
213:3
207:q
185:4
177:3
171:p
151:q
131:p
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.