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