2840:
2371:
2835:{\displaystyle {\begin{aligned}\left({\frac {s+2r}{n}}\right)&=\left({\frac {t+at^{-1}+2r}{n}}\right)=\left({\frac {t\left(1+at^{-2}+2rt^{-1}\right)}{n}}\right)\\&=\left({\frac {t\left(1+r^{2}t^{-2}+2rt^{-1}\right)}{n}}\right)=\left({\frac {t\left(1+rt^{-1}\right)^{2}}{n}}\right)\\&=\left({\frac {t}{n}}\right)\left({\frac {1+rt^{-1}}{n}}\right)^{2}=\left({\frac {t}{n}}\right)(\pm 1)^{2}=\left({\frac {t}{n}}\right)\end{aligned}}}
2313:
1887:
2308:{\displaystyle {\begin{aligned}r^{2}&=\left(a^{(n+5-p-q)/8}\right)^{2}\\&=\left(a^{(n+5-p-q-\Phi (n))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-(p-1)(q-1))/8}\right)^{2}\\&=\left(a^{(n+5-p-q-n+p+q-1)/8}\right)^{2}\\&=\left(a^{4/8}\right)^{2}\\&=\pm a\end{aligned}}}
2940:
A major disadvantage of this scheme is that it can encrypt messages only bit per bit - therefore, it is only suitable for small data packets like a session key. To illustrate, consider a 128 bit key that is transmitted using a 1024 bit modulus. Then, one has to send
1734:
216:
285:
1655:
1043:
137:
929:
847:
388:
1580:
521:
2376:
1892:
1429:
1123:
1660:
739:
626:
572:
1180:
1385:
1310:
958:
879:
797:
1241:
80:
2363:
1879:
1781:
764:
707:
413:
319:
2922:
2900:
2878:
2338:
1854:
1832:
1807:
1756:
682:
651:
435:
345:
1343:
2972:
This scheme does not preserve key-privacy, i.e. a passive adversary can recover meaningful information about the identity of the recipient observing the ciphertext.
145:
1522:
1456:
1264:
2959:
1499:
1479:
1524:. In this case we have to send a ciphertext for both cases. As soon as this information is known to the encrypting entity, only one element needs to be sent.
224:
1585:
3017:
2925:
2991:
966:
85:
884:
802:
350:
1535:
443:
2851:
31:
1729:{\displaystyle \textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)}
1393:
1048:
712:
577:
526:
23:
1131:
1348:
1273:
934:
855:
773:
1194:
54:
2343:
1859:
1761:
744:
687:
393:
299:
2905:
2883:
2861:
2321:
1837:
1815:
1790:
1739:
665:
634:
418:
328:
2855:
2941:
2 × 128 × 1024 bit = 32 KByte (when it is not known whether
1784:
1459:
1315:
211:{\displaystyle \textstyle {\mathcal {M}}=\left\{-1,1\right\},{\mathcal {C}}=\mathbb {Z} _{n}}
2995:
2988:
2969:), which is only acceptable for environments in which session keys change infrequently.
1504:
1438:
1246:
2944:
1484:
1464:
321:
wants to obtain his private key, he contacts the PKG through a secure channel. The PKG
27:
3011:
2929:
1435:
Note that here we are assuming that the encrypting entity does not know whether
280:{\displaystyle \textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}}
3000:
Proceedings of the 8th IMA International
Conference on Cryptography and Coding
2928:
can be mounted by altering packets that transmit a single bit and using the
1650:{\displaystyle \left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1}
2854:, which is suspected to be very hard. The common rules for choosing a
2850:
It can be shown that breaking the scheme is equivalent to solving the
2902:
uniform and random and moreover include some authenticity checks for
30:
in 2001. The security of the scheme is based on the hardness of the
2989:
An
Identity Based Encryption Scheme Based on Quadratic Residues
1038:{\displaystyle \textstyle c_{1}=t_{1}+at_{1}^{-1}{\pmod {n}}}
132:{\displaystyle \textstyle p,q,\,p\equiv q\equiv 3{\bmod {4}}}
119:
924:{\displaystyle \textstyle m=\left({\frac {t_{2}}{n}}\right)}
842:{\displaystyle \textstyle m=\left({\frac {t_{1}}{n}}\right)}
725:
187:
152:
383:{\displaystyle \textstyle \left({\frac {a}{n}}\right)=1}
1575:{\displaystyle \textstyle p\equiv q\equiv 3{\pmod {4}}}
516:{\displaystyle \textstyle r=a^{(n+5-p-q)/8}{\pmod {n}}}
2909:
2887:
2865:
2347:
2325:
1863:
1841:
1819:
1794:
1765:
1743:
1664:
1539:
1135:
970:
938:
888:
859:
806:
777:
748:
716:
691:
669:
638:
581:
530:
447:
422:
397:
354:
332:
303:
228:
149:
89:
58:
2947:
2908:
2886:
2864:
2374:
2346:
2324:
1890:
1862:
1840:
1818:
1793:
1764:
1742:
1663:
1588:
1538:
1507:
1487:
1467:
1441:
1396:
1351:
1318:
1276:
1249:
1197:
1134:
1051:
969:
937:
887:
858:
805:
776:
747:
715:
690:
668:
637:
580:
529:
446:
421:
396:
353:
331:
302:
227:
148:
88:
57:
1424:{\displaystyle m=\left({\frac {\alpha }{n}}\right)}
2953:
2916:
2894:
2872:
2834:
2357:
2332:
2307:
1873:
1848:
1826:
1801:
1775:
1750:
1728:
1649:
1574:
1516:
1493:
1473:
1450:
1423:
1379:
1337:
1304:
1258:
1235:
1174:
1118:{\displaystyle c_{2}=t_{2}-at_{2}^{-1}{\pmod {n}}}
1117:
1037:
952:
923:
873:
841:
791:
758:
733:
701:
676:
645:
620:
566:
515:
429:
407:
382:
339:
313:
279:
210:
131:
74:
734:{\displaystyle \textstyle m\in {\mathcal {M}}}
621:{\displaystyle \textstyle r^{2}=-a{\pmod {n}}}
2932:to observe the effect on the decrypted bit).
567:{\displaystyle \textstyle r^{2}=a{\pmod {n}}}
8:
2340:is a quadratic residue, same idea holds for
1175:{\displaystyle \textstyle s=(c_{1},c_{2})}
2946:
2907:
2885:
2863:
2814:
2801:
2774:
2761:
2742:
2726:
2707:
2677:
2663:
2638:
2607:
2585:
2575:
2554:
2516:
2494:
2470:
2435:
2419:
2383:
2375:
2373:
2345:
2323:
2279:
2265:
2261:
2236:
2222:
2170:
2145:
2131:
2070:
2045:
2031:
1988:
1963:
1949:
1921:
1899:
1891:
1889:
1861:
1839:
1817:
1792:
1763:
1741:
1711:
1690:
1669:
1662:
1619:
1593:
1587:
1555:
1537:
1506:
1486:
1466:
1440:
1407:
1395:
1362:
1350:
1323:
1317:
1287:
1275:
1248:
1224:
1211:
1196:
1162:
1149:
1133:
1099:
1090:
1085:
1069:
1056:
1050:
1018:
1009:
1004:
988:
975:
968:
943:
936:
905:
899:
886:
864:
857:
823:
817:
804:
782:
775:
746:
724:
723:
714:
689:
667:
636:
601:
586:
579:
547:
535:
528:
496:
486:
458:
445:
420:
395:
359:
352:
330:
301:
270:
266:
265:
255:
226:
201:
197:
196:
186:
185:
151:
150:
147:
122:
118:
102:
87:
56:
2980:
7:
1563:
1556:
1107:
1026:
1019:
609:
602:
555:
548:
504:
497:
2016:
14:
2926:adaptive chosen ciphertext attack
142:the message and the cipher space
1380:{\displaystyle \alpha =c_{2}+2r}
1305:{\displaystyle \alpha =c_{1}+2r}
953:{\displaystyle \textstyle t_{1}}
874:{\displaystyle \textstyle t_{2}}
792:{\displaystyle \textstyle t_{1}}
390:by a deterministic process from
16:Identity based encryption system
1236:{\displaystyle s=(c_{1},c_{2})}
1100:
75:{\displaystyle \textstyle n=pq}
2798:
2788:
2219:
2171:
2128:
2125:
2113:
2110:
2098:
2071:
2028:
2025:
2019:
1989:
1946:
1922:
1683:
1567:
1557:
1230:
1204:
1168:
1142:
1111:
1101:
1030:
1020:
613:
603:
559:
549:
508:
498:
483:
459:
415:(e.g. multiple application of
261:
221:a secure public hash function
1:
2852:quadratic residuosity problem
2358:{\displaystyle \textstyle -a}
2318:Moreover, (for the case that
1874:{\displaystyle \textstyle -a}
1776:{\displaystyle \textstyle -a}
759:{\displaystyle \textstyle ID}
702:{\displaystyle \textstyle -1}
408:{\displaystyle \textstyle ID}
314:{\displaystyle \textstyle ID}
32:quadratic residuosity problem
2917:{\displaystyle \textstyle t}
2895:{\displaystyle \textstyle t}
2873:{\displaystyle \textstyle n}
2333:{\displaystyle \textstyle a}
1849:{\displaystyle \textstyle a}
1827:{\displaystyle \textstyle r}
1802:{\displaystyle \textstyle n}
1751:{\displaystyle \textstyle a}
677:{\displaystyle \textstyle 1}
646:{\displaystyle \textstyle r}
430:{\displaystyle \textstyle f}
340:{\displaystyle \textstyle a}
3018:Identity-based cryptography
662:To encrypt a bit (coded as
3034:
139:are prime and kept secret,
24:identity based encryption
1191:To decrypt a ciphertext
1338:{\displaystyle r^{2}=a}
2955:
2918:
2896:
2874:
2836:
2359:
2334:
2309:
1875:
1850:
1828:
1803:
1777:
1752:
1730:
1651:
1576:
1532:First note that since
1518:
1495:
1475:
1452:
1425:
1381:
1339:
1306:
1260:
1237:
1176:
1119:
1039:
954:
925:
875:
843:
793:
760:
735:
703:
678:
647:
622:
568:
523:(which fulfils either
517:
431:
409:
384:
341:
315:
281:
212:
133:
76:
2956:
2919:
2897:
2880:, make the choice of
2875:
2837:
2360:
2335:
2310:
1876:
1851:
1829:
1804:
1778:
1753:
1731:
1652:
1577:
1519:
1496:
1476:
1453:
1426:
1382:
1340:
1307:
1261:
1238:
1177:
1120:
1040:
955:
926:
876:
844:
794:
761:
736:
704:
679:
648:
623:
569:
518:
432:
410:
385:
342:
316:
282:
213:
134:
77:
51:a public RSA-modulus
2945:
2906:
2884:
2862:
2372:
2344:
2322:
1888:
1860:
1838:
1834:is a square root of
1816:
1791:
1762:
1740:
1661:
1586:
1536:
1505:
1485:
1465:
1439:
1394:
1349:
1316:
1274:
1247:
1195:
1132:
1049:
967:
935:
885:
856:
803:
774:
745:
713:
688:
666:
635:
578:
527:
444:
419:
394:
351:
329:
300:
225:
146:
86:
55:
2858:hold: Use a secure
1098:
1017:
26:system proposed by
2994:2007-02-06 at the
2951:
2914:
2913:
2892:
2891:
2870:
2869:
2832:
2830:
2355:
2354:
2330:
2329:
2305:
2303:
1871:
1870:
1846:
1845:
1824:
1823:
1799:
1798:
1773:
1772:
1748:
1747:
1726:
1725:
1647:
1572:
1571:
1517:{\displaystyle -a}
1514:
1491:
1471:
1451:{\displaystyle ID}
1448:
1421:
1377:
1335:
1302:
1259:{\displaystyle ID}
1256:
1233:
1172:
1171:
1115:
1081:
1035:
1034:
1000:
950:
949:
931:, different from
921:
920:
871:
870:
839:
838:
789:
788:
756:
755:
731:
730:
699:
698:
674:
673:
643:
642:
618:
617:
564:
563:
513:
512:
427:
426:
405:
404:
380:
379:
337:
336:
311:
310:
277:
276:
208:
207:
129:
128:
72:
71:
2961:is the square of
2954:{\displaystyle r}
2822:
2782:
2755:
2715:
2687:
2625:
2534:
2457:
2402:
1785:quadratic residue
1719:
1698:
1677:
1632:
1606:
1494:{\displaystyle a}
1474:{\displaystyle r}
1415:
914:
832:
367:
47:The PKG chooses:
3025:
3003:
2987:Clifford Cocks,
2985:
2960:
2958:
2957:
2952:
2923:
2921:
2920:
2915:
2901:
2899:
2898:
2893:
2879:
2877:
2876:
2871:
2841:
2839:
2838:
2833:
2831:
2827:
2823:
2815:
2806:
2805:
2787:
2783:
2775:
2766:
2765:
2760:
2756:
2751:
2750:
2749:
2727:
2720:
2716:
2708:
2696:
2692:
2688:
2683:
2682:
2681:
2676:
2672:
2671:
2670:
2639:
2630:
2626:
2621:
2620:
2616:
2615:
2614:
2593:
2592:
2580:
2579:
2555:
2543:
2539:
2535:
2530:
2529:
2525:
2524:
2523:
2502:
2501:
2471:
2462:
2458:
2453:
2443:
2442:
2420:
2407:
2403:
2398:
2384:
2364:
2362:
2361:
2356:
2339:
2337:
2336:
2331:
2314:
2312:
2311:
2306:
2304:
2288:
2284:
2283:
2278:
2274:
2273:
2269:
2245:
2241:
2240:
2235:
2231:
2230:
2226:
2154:
2150:
2149:
2144:
2140:
2139:
2135:
2054:
2050:
2049:
2044:
2040:
2039:
2035:
1972:
1968:
1967:
1962:
1958:
1957:
1953:
1904:
1903:
1880:
1878:
1877:
1872:
1855:
1853:
1852:
1847:
1833:
1831:
1830:
1825:
1808:
1806:
1805:
1800:
1782:
1780:
1779:
1774:
1757:
1755:
1754:
1749:
1735:
1733:
1732:
1727:
1724:
1720:
1712:
1703:
1699:
1691:
1682:
1678:
1670:
1656:
1654:
1653:
1648:
1637:
1633:
1628:
1620:
1611:
1607:
1602:
1594:
1581:
1579:
1578:
1573:
1570:
1523:
1521:
1520:
1515:
1500:
1498:
1497:
1492:
1480:
1478:
1477:
1472:
1457:
1455:
1454:
1449:
1430:
1428:
1427:
1422:
1420:
1416:
1408:
1386:
1384:
1383:
1378:
1367:
1366:
1344:
1342:
1341:
1336:
1328:
1327:
1311:
1309:
1308:
1303:
1292:
1291:
1265:
1263:
1262:
1257:
1242:
1240:
1239:
1234:
1229:
1228:
1216:
1215:
1181:
1179:
1178:
1173:
1167:
1166:
1154:
1153:
1124:
1122:
1121:
1116:
1114:
1097:
1089:
1074:
1073:
1061:
1060:
1044:
1042:
1041:
1036:
1033:
1016:
1008:
993:
992:
980:
979:
959:
957:
956:
951:
948:
947:
930:
928:
927:
922:
919:
915:
910:
909:
900:
880:
878:
877:
872:
869:
868:
848:
846:
845:
840:
837:
833:
828:
827:
818:
798:
796:
795:
790:
787:
786:
765:
763:
762:
757:
740:
738:
737:
732:
729:
728:
708:
706:
705:
700:
683:
681:
680:
675:
652:
650:
649:
644:
628:, see below) and
627:
625:
624:
619:
616:
591:
590:
573:
571:
570:
565:
562:
540:
539:
522:
520:
519:
514:
511:
495:
494:
490:
436:
434:
433:
428:
414:
412:
411:
406:
389:
387:
386:
381:
372:
368:
360:
346:
344:
343:
338:
320:
318:
317:
312:
286:
284:
283:
278:
275:
274:
269:
260:
259:
254:
250:
217:
215:
214:
209:
206:
205:
200:
191:
190:
181:
177:
156:
155:
138:
136:
135:
130:
127:
126:
81:
79:
78:
73:
20:Cocks IBE scheme
3033:
3032:
3028:
3027:
3026:
3024:
3023:
3022:
3008:
3007:
3006:
2996:Wayback Machine
2986:
2982:
2978:
2943:
2942:
2938:
2924:(otherwise, an
2904:
2903:
2882:
2881:
2860:
2859:
2848:
2829:
2828:
2810:
2797:
2770:
2738:
2728:
2722:
2721:
2703:
2694:
2693:
2659:
2649:
2645:
2644:
2640:
2634:
2603:
2581:
2571:
2564:
2560:
2556:
2550:
2541:
2540:
2512:
2490:
2480:
2476:
2472:
2466:
2431:
2421:
2415:
2408:
2385:
2379:
2370:
2369:
2342:
2341:
2320:
2319:
2302:
2301:
2286:
2285:
2257:
2253:
2252:
2243:
2242:
2166:
2162:
2161:
2152:
2151:
2066:
2062:
2061:
2052:
2051:
1984:
1980:
1979:
1970:
1969:
1917:
1913:
1912:
1905:
1895:
1886:
1885:
1858:
1857:
1836:
1835:
1814:
1813:
1789:
1788:
1760:
1759:
1738:
1737:
1707:
1686:
1665:
1659:
1658:
1621:
1615:
1595:
1589:
1584:
1583:
1534:
1533:
1530:
1503:
1502:
1483:
1482:
1463:
1462:
1437:
1436:
1403:
1392:
1391:
1358:
1347:
1346:
1319:
1314:
1313:
1283:
1272:
1271:
1245:
1244:
1220:
1207:
1193:
1192:
1189:
1158:
1145:
1130:
1129:
1065:
1052:
1047:
1046:
984:
971:
965:
964:
939:
933:
932:
901:
895:
883:
882:
860:
854:
853:
852:chooses random
819:
813:
801:
800:
778:
772:
771:
770:chooses random
743:
742:
711:
710:
686:
685:
664:
663:
660:
633:
632:
582:
576:
575:
531:
525:
524:
454:
442:
441:
417:
416:
392:
391:
355:
349:
348:
327:
326:
298:
297:
294:
264:
240:
236:
235:
223:
222:
195:
164:
160:
144:
143:
84:
83:
53:
52:
45:
40:
17:
12:
11:
5:
3031:
3029:
3021:
3020:
3010:
3009:
3005:
3004:
2979:
2977:
2974:
2950:
2937:
2934:
2912:
2890:
2868:
2847:
2844:
2843:
2842:
2826:
2821:
2818:
2813:
2809:
2804:
2800:
2796:
2793:
2790:
2786:
2781:
2778:
2773:
2769:
2764:
2759:
2754:
2748:
2745:
2741:
2737:
2734:
2731:
2725:
2719:
2714:
2711:
2706:
2702:
2699:
2697:
2695:
2691:
2686:
2680:
2675:
2669:
2666:
2662:
2658:
2655:
2652:
2648:
2643:
2637:
2633:
2629:
2624:
2619:
2613:
2610:
2606:
2602:
2599:
2596:
2591:
2588:
2584:
2578:
2574:
2570:
2567:
2563:
2559:
2553:
2549:
2546:
2544:
2542:
2538:
2533:
2528:
2522:
2519:
2515:
2511:
2508:
2505:
2500:
2497:
2493:
2489:
2486:
2483:
2479:
2475:
2469:
2465:
2461:
2456:
2452:
2449:
2446:
2441:
2438:
2434:
2430:
2427:
2424:
2418:
2414:
2411:
2409:
2406:
2401:
2397:
2394:
2391:
2388:
2382:
2378:
2377:
2353:
2350:
2328:
2316:
2315:
2300:
2297:
2294:
2291:
2289:
2287:
2282:
2277:
2272:
2268:
2264:
2260:
2256:
2251:
2248:
2246:
2244:
2239:
2234:
2229:
2225:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2169:
2165:
2160:
2157:
2155:
2153:
2148:
2143:
2138:
2134:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2076:
2073:
2069:
2065:
2060:
2057:
2055:
2053:
2048:
2043:
2038:
2034:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1987:
1983:
1978:
1975:
1973:
1971:
1966:
1961:
1956:
1952:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1920:
1916:
1911:
1908:
1906:
1902:
1898:
1894:
1893:
1869:
1866:
1844:
1822:
1797:
1771:
1768:
1746:
1723:
1718:
1715:
1710:
1706:
1702:
1697:
1694:
1689:
1685:
1681:
1676:
1673:
1668:
1646:
1643:
1640:
1636:
1631:
1627:
1624:
1618:
1614:
1610:
1605:
1601:
1598:
1592:
1569:
1566:
1562:
1559:
1554:
1551:
1548:
1545:
1542:
1529:
1526:
1513:
1510:
1490:
1470:
1447:
1444:
1433:
1432:
1419:
1414:
1411:
1406:
1402:
1399:
1388:
1387:otherwise, and
1376:
1373:
1370:
1365:
1361:
1357:
1354:
1334:
1331:
1326:
1322:
1301:
1298:
1295:
1290:
1286:
1282:
1279:
1255:
1252:
1232:
1227:
1223:
1219:
1214:
1210:
1206:
1203:
1200:
1188:
1185:
1184:
1183:
1170:
1165:
1161:
1157:
1152:
1148:
1144:
1141:
1138:
1126:
1113:
1110:
1106:
1103:
1096:
1093:
1088:
1084:
1080:
1077:
1072:
1068:
1064:
1059:
1055:
1032:
1029:
1025:
1022:
1015:
1012:
1007:
1003:
999:
996:
991:
987:
983:
978:
974:
961:
946:
942:
918:
913:
908:
904:
898:
894:
891:
867:
863:
850:
836:
831:
826:
822:
816:
812:
809:
785:
781:
754:
751:
727:
722:
719:
697:
694:
672:
659:
656:
655:
654:
641:
629:
615:
612:
608:
605:
600:
597:
594:
589:
585:
561:
558:
554:
551:
546:
543:
538:
534:
510:
507:
503:
500:
493:
489:
485:
482:
479:
476:
473:
470:
467:
464:
461:
457:
453:
450:
438:
425:
403:
400:
378:
375:
371:
366:
363:
358:
335:
309:
306:
293:
290:
289:
288:
273:
268:
263:
258:
253:
249:
246:
243:
239:
234:
231:
219:
204:
199:
194:
189:
184:
180:
176:
173:
170:
167:
163:
159:
154:
140:
125:
121:
117:
114:
111:
108:
105:
101:
98:
95:
92:
70:
67:
64:
61:
44:
41:
39:
36:
28:Clifford Cocks
15:
13:
10:
9:
6:
4:
3:
2:
3030:
3019:
3016:
3015:
3013:
3001:
2997:
2993:
2990:
2984:
2981:
2975:
2973:
2970:
2968:
2964:
2948:
2935:
2933:
2931:
2927:
2910:
2888:
2866:
2857:
2853:
2845:
2824:
2819:
2816:
2811:
2807:
2802:
2794:
2791:
2784:
2779:
2776:
2771:
2767:
2762:
2757:
2752:
2746:
2743:
2739:
2735:
2732:
2729:
2723:
2717:
2712:
2709:
2704:
2700:
2698:
2689:
2684:
2678:
2673:
2667:
2664:
2660:
2656:
2653:
2650:
2646:
2641:
2635:
2631:
2627:
2622:
2617:
2611:
2608:
2604:
2600:
2597:
2594:
2589:
2586:
2582:
2576:
2572:
2568:
2565:
2561:
2557:
2551:
2547:
2545:
2536:
2531:
2526:
2520:
2517:
2513:
2509:
2506:
2503:
2498:
2495:
2491:
2487:
2484:
2481:
2477:
2473:
2467:
2463:
2459:
2454:
2450:
2447:
2444:
2439:
2436:
2432:
2428:
2425:
2422:
2416:
2412:
2410:
2404:
2399:
2395:
2392:
2389:
2386:
2380:
2368:
2367:
2366:
2351:
2348:
2326:
2298:
2295:
2292:
2290:
2280:
2275:
2270:
2266:
2262:
2258:
2254:
2249:
2247:
2237:
2232:
2227:
2223:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2167:
2163:
2158:
2156:
2146:
2141:
2136:
2132:
2122:
2119:
2116:
2107:
2104:
2101:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2074:
2067:
2063:
2058:
2056:
2046:
2041:
2036:
2032:
2022:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1985:
1981:
1976:
1974:
1964:
1959:
1954:
1950:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1918:
1914:
1909:
1907:
1900:
1896:
1884:
1883:
1882:
1867:
1864:
1842:
1820:
1810:
1795:
1786:
1769:
1766:
1744:
1721:
1716:
1713:
1708:
1704:
1700:
1695:
1692:
1687:
1679:
1674:
1671:
1666:
1644:
1641:
1638:
1634:
1629:
1625:
1622:
1616:
1612:
1608:
1603:
1599:
1596:
1590:
1564:
1560:
1552:
1549:
1546:
1543:
1540:
1527:
1525:
1511:
1508:
1488:
1468:
1461:
1445:
1442:
1417:
1412:
1409:
1404:
1400:
1397:
1389:
1374:
1371:
1368:
1363:
1359:
1355:
1352:
1332:
1329:
1324:
1320:
1299:
1296:
1293:
1288:
1284:
1280:
1277:
1269:
1268:
1267:
1253:
1250:
1225:
1221:
1217:
1212:
1208:
1201:
1198:
1186:
1163:
1159:
1155:
1150:
1146:
1139:
1136:
1127:
1108:
1104:
1094:
1091:
1086:
1082:
1078:
1075:
1070:
1066:
1062:
1057:
1053:
1027:
1023:
1013:
1010:
1005:
1001:
997:
994:
989:
985:
981:
976:
972:
962:
944:
940:
916:
911:
906:
902:
896:
892:
889:
865:
861:
851:
834:
829:
824:
820:
814:
810:
807:
783:
779:
769:
768:
767:
752:
749:
720:
717:
695:
692:
670:
657:
639:
630:
610:
606:
598:
595:
592:
587:
583:
556:
552:
544:
541:
536:
532:
505:
501:
491:
487:
480:
477:
474:
471:
468:
465:
462:
455:
451:
448:
439:
423:
401:
398:
376:
373:
369:
364:
361:
356:
333:
324:
323:
322:
307:
304:
291:
271:
256:
251:
247:
244:
241:
237:
232:
229:
220:
202:
192:
182:
178:
174:
171:
168:
165:
161:
157:
141:
123:
115:
112:
109:
106:
103:
99:
96:
93:
90:
68:
65:
62:
59:
50:
49:
48:
42:
37:
35:
33:
29:
25:
21:
2999:
2983:
2971:
2966:
2962:
2939:
2849:
2317:
1811:
1531:
1434:
1190:
1182:to the user.
661:
653:to the user.
295:
46:
19:
18:
2856:RSA modulus
1812:Therefore,
1528:Correctness
1460:square root
766:, the user
2976:References
631:transmits
296:When user
2792:±
2744:−
2665:−
2609:−
2587:−
2518:−
2496:−
2437:−
2349:−
2296:±
2214:−
2196:−
2190:−
2184:−
2120:−
2105:−
2096:−
2090:−
2084:−
2017:Φ
2014:−
2008:−
2002:−
1941:−
1935:−
1865:−
1767:−
1736:, either
1684:⇒
1642:−
1623:−
1597:−
1550:≡
1544:≡
1509:−
1410:α
1390:computes
1353:α
1278:α
1270:computes
1243:for user
1092:−
1076:−
1011:−
963:computes
721:∈
693:−
596:−
478:−
472:−
440:computes
262:→
257:∗
166:−
113:≡
107:≡
3012:Category
2992:Archived
2936:Problems
2846:Security
1458:has the
325:derives
82:, where
38:Protocol
1787:modulo
1657:) and
1187:Decrypt
658:Encrypt
292:Extract
3002:, 2001
2930:oracle
1582:(i.e.
1128:sends
22:is an
1783:is a
1266:, he
1045:and
881:with
799:with
347:with
43:Setup
2965:or −
741:for
2365:):
1856:or
1758:or
1561:mod
1501:or
1481:of
1345:or
1312:if
1125:and
1105:mod
1024:mod
607:mod
574:or
553:mod
502:mod
218:and
120:mod
3014::
2998:,
1881::
1809:.
709:)
437:),
34:.
2967:a
2963:a
2949:r
2911:t
2889:t
2867:n
2825:)
2820:n
2817:t
2812:(
2808:=
2803:2
2799:)
2795:1
2789:(
2785:)
2780:n
2777:t
2772:(
2768:=
2763:2
2758:)
2753:n
2747:1
2740:t
2736:r
2733:+
2730:1
2724:(
2718:)
2713:n
2710:t
2705:(
2701:=
2690:)
2685:n
2679:2
2674:)
2668:1
2661:t
2657:r
2654:+
2651:1
2647:(
2642:t
2636:(
2632:=
2628:)
2623:n
2618:)
2612:1
2605:t
2601:r
2598:2
2595:+
2590:2
2583:t
2577:2
2573:r
2569:+
2566:1
2562:(
2558:t
2552:(
2548:=
2537:)
2532:n
2527:)
2521:1
2514:t
2510:r
2507:2
2504:+
2499:2
2492:t
2488:a
2485:+
2482:1
2478:(
2474:t
2468:(
2464:=
2460:)
2455:n
2451:r
2448:2
2445:+
2440:1
2433:t
2429:a
2426:+
2423:t
2417:(
2413:=
2405:)
2400:n
2396:r
2393:2
2390:+
2387:s
2381:(
2352:a
2327:a
2299:a
2293:=
2281:2
2276:)
2271:8
2267:/
2263:4
2259:a
2255:(
2250:=
2238:2
2233:)
2228:8
2224:/
2220:)
2217:1
2211:q
2208:+
2205:p
2202:+
2199:n
2193:q
2187:p
2181:5
2178:+
2175:n
2172:(
2168:a
2164:(
2159:=
2147:2
2142:)
2137:8
2133:/
2129:)
2126:)
2123:1
2117:q
2114:(
2111:)
2108:1
2102:p
2099:(
2093:q
2087:p
2081:5
2078:+
2075:n
2072:(
2068:a
2064:(
2059:=
2047:2
2042:)
2037:8
2033:/
2029:)
2026:)
2023:n
2020:(
2011:q
2005:p
1999:5
1996:+
1993:n
1990:(
1986:a
1982:(
1977:=
1965:2
1960:)
1955:8
1951:/
1947:)
1944:q
1938:p
1932:5
1929:+
1926:n
1923:(
1919:a
1915:(
1910:=
1901:2
1897:r
1868:a
1843:a
1821:r
1796:n
1770:a
1745:a
1722:)
1717:q
1714:a
1709:(
1705:=
1701:)
1696:p
1693:a
1688:(
1680:)
1675:n
1672:a
1667:(
1645:1
1639:=
1635:)
1630:q
1626:1
1617:(
1613:=
1609:)
1604:p
1600:1
1591:(
1568:)
1565:4
1558:(
1553:3
1547:q
1541:p
1512:a
1489:a
1469:r
1446:D
1443:I
1431:.
1418:)
1413:n
1405:(
1401:=
1398:m
1375:r
1372:2
1369:+
1364:2
1360:c
1356:=
1333:a
1330:=
1325:2
1321:r
1300:r
1297:2
1294:+
1289:1
1285:c
1281:=
1254:D
1251:I
1231:)
1226:2
1222:c
1218:,
1213:1
1209:c
1205:(
1202:=
1199:s
1169:)
1164:2
1160:c
1156:,
1151:1
1147:c
1143:(
1140:=
1137:s
1112:)
1109:n
1102:(
1095:1
1087:2
1083:t
1079:a
1071:2
1067:t
1063:=
1058:2
1054:c
1031:)
1028:n
1021:(
1014:1
1006:1
1002:t
998:a
995:+
990:1
986:t
982:=
977:1
973:c
960:,
945:1
941:t
917:)
912:n
907:2
903:t
897:(
893:=
890:m
866:2
862:t
849:,
835:)
830:n
825:1
821:t
815:(
811:=
808:m
784:1
780:t
753:D
750:I
726:M
718:m
696:1
684:/
671:1
640:r
614:)
611:n
604:(
599:a
593:=
588:2
584:r
560:)
557:n
550:(
545:a
542:=
537:2
533:r
509:)
506:n
499:(
492:8
488:/
484:)
481:q
475:p
469:5
466:+
463:n
460:(
456:a
452:=
449:r
424:f
402:D
399:I
377:1
374:=
370:)
365:n
362:a
357:(
334:a
308:D
305:I
287:.
272:n
267:Z
252:}
248:1
245:,
242:0
238:{
233::
230:f
203:n
198:Z
193:=
188:C
183:,
179:}
175:1
172:,
169:1
162:{
158:=
153:M
124:4
116:3
110:q
104:p
100:,
97:q
94:,
91:p
69:q
66:p
63:=
60:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.