3369:
320:
It is not necessary to come up with a group and generator for each new key. Indeed, one may expect a specific implementation of ElGamal to be hardcoded to use a specific group, or a group from a specific suite. The choice of group is mostly about how large keys you want to
2235:; however, these exponentiations are independent of the message and can be computed ahead of time if needed. Decryption requires one exponentiation and one computation of a group inverse, which can, however, be easily combined into just one exponentiation.
193:
for encrypting the message. ElGamal encryption is performed in three phases: the key generation, the encryption, and the decryption. The first is purely key exchange, whereas the latter two mix key exchange computations with message computations.
1929:, where the message itself is encrypted using a symmetric cryptosystem, and ElGamal is then used to encrypt only the symmetric key. This is because asymmetric cryptosystems like ElGamal are usually slower than symmetric ones for the same
1933:, so it is faster to encrypt the message, which can be arbitrarily large, with a symmetric cipher, and then use ElGamal only to encrypt the symmetric key, which usually is quite small compared to the size of the message.
1665:
1871:
2176:
To achieve chosen-ciphertext security, the scheme must be further modified, or an appropriate padding scheme must be used. Depending on the modification, the DDH assumption may or may not be necessary.
1299:
1717:
1018:
705:
388:
830:
2148:
1776:
2079:
1136:
929:
879:
1198:
788:
1508:
1238:
574:
477:
741:
424:
2228:
can be encrypted to many possible ciphertexts, with the consequence that a general ElGamal encryption produces a 1:2 expansion in size from plaintext to ciphertext.
1470:
1332:
252:
228:
2171:
2202:
2099:
2014:
1983:
1959:
1914:
1894:
1737:
1528:
1432:
1412:
1392:
1372:
1352:
1156:
1078:
1058:
1038:
969:
949:
661:
638:
618:
598:
530:
497:
344:
315:
295:
275:
187:
155:
105:
3349:
3179:
2809:
2519:
1537:
2937:
3032:
2401:
2932:
1962:
1781:
2661:
2405:
108:
2840:
2834:
2021:
1993:
3397:
2958:
2512:
2477:
2440:
2316:
1531:
46:
2576:
2180:
Other schemes related to ElGamal which achieve security against chosen ciphertext attacks have also been proposed. The
3025:
2644:
2601:
2566:
2556:
2505:
2720:
2634:
2581:
54:
3228:
2745:
1435:
169:
The algorithm can be described as first performing a Diffie–Hellman key exchange to establish a shared secret
2629:
2181:
1243:
3018:
2886:
2819:
2209:
1439:
1673:
3344:
3299:
3112:
2983:
2876:
2725:
2639:
2561:
2028:
974:
74:
3223:
2735:
2624:
2606:
666:
349:
2341:
3339:
2988:
2968:
796:
255:
2871:
2361:
2299:
2104:
1742:
3329:
3319:
3174:
2927:
2698:
2250:
2221:
2038:
2032:
1095:
888:
838:
78:
31:
17:
1165:
753:
3324:
3314:
3117:
3077:
3070:
3060:
3055:
2881:
2528:
2409:
1475:
1203:
50:
3065:
2963:
2814:
2753:
2688:
2356:
2294:
2255:
535:
438:
713:
396:
3372:
3218:
3164:
2829:
2586:
2543:
2457:
2020:. Semantic security is not implied by the computational Diffie–Hellman assumption alone. See
1445:
1307:
3334:
3258:
2740:
2551:
2423:
Tsiounis, Yiannis; Yung, Moti (2006-05-24). "On the security of ElGamal based encryption".
231:
8:
3097:
2846:
2205:
1926:
236:
212:
66:
2153:
3203:
3187:
3134:
2616:
2596:
2591:
2571:
2374:
2288:
2187:
2084:
1999:
1968:
1944:
1899:
1879:
1722:
1513:
1417:
1397:
1377:
1357:
1337:
1141:
1063:
1043:
1023:
954:
934:
646:
623:
603:
583:
515:
482:
329:
300:
280:
260:
172:
158:
140:
90:
3263:
3253:
3124:
2953:
2896:
2824:
2710:
2473:
2436:
2312:
2017:
1941:
The security of the ElGamal scheme depends on the properties of the underlying group
1930:
62:
1925:
Like most public key systems, the ElGamal cryptosystem is usually used as part of a
3198:
2799:
2465:
2428:
2378:
2366:
2304:
1986:
2269:
3273:
3193:
3154:
3102:
3087:
2342:"A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms"
2232:
2212:, whose proof requires an assumption that is stronger than the DDH assumption.
3391:
3354:
3309:
3268:
3248:
3144:
3107:
3082:
2469:
2370:
2244:
1660:{\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}
1081:
58:
3304:
3149:
3139:
3129:
3092:
3041:
2993:
2973:
1301:, and thus it is the same shared secret that was used by Bob in encryption.
207:
190:
85:
70:
38:
3283:
2891:
2768:
2267:
3243:
3213:
3208:
3169:
2917:
2649:
2464:. Lecture Notes in Computer Science. Vol. 2020. pp. 143–158.
2432:
2427:. Lecture Notes in Computer Science. Vol. 1431. pp. 117–134.
2308:
431:
3233:
2671:
2293:. Lecture Notes in Computer Science. Vol. 1423. pp. 48–63.
2284:
2225:
2024:
for a discussion of groups where the assumption is believed to hold.
1060:
is generated for every message to improve security. For this reason,
3278:
3238:
2978:
2912:
2783:
2778:
2773:
2676:
2654:
1866:{\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}
137:. Its security depends upon the difficulty of a certain problem in
2804:
2763:
2458:"The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES"
2456:
Abdalla, Michel; Bellare, Mihir; Rogaway, Phillip (2001-01-01).
2184:
is secure under chosen ciphertext attack assuming DDH holds for
1394:
is a subgroup of a multiplicative group of integers modulo
3159:
2922:
2384:
2758:
2715:
2683:
2666:
1961:
as well as any padding scheme used on the messages. If the
2851:
2705:
202:
The first party, Alice, generates a key pair as follows:
81:, which should not be confused with ElGamal encryption.
30:"ElGamal" redirects here. For signature algorithm, see
3180:
Cryptographically secure pseudorandom number generator
2455:
2190:
2156:
2107:
2087:
2041:
2002:
1971:
1947:
1902:
1882:
1784:
1745:
1725:
1676:
1540:
1516:
1478:
1448:
1420:
1400:
1380:
1360:
1340:
1310:
1246:
1206:
1168:
1144:
1098:
1066:
1046:
1026:
977:
957:
937:
891:
841:
799:
756:
716:
669:
649:
626:
606:
586:
538:
518:
485:
441:
399:
352:
332:
303:
283:
263:
239:
215:
175:
143:
93:
2489:
2268:A. J. Menezes; P. C. van Oorschot; S. A. Vanstone.
2196:
2165:
2142:
2093:
2073:
2008:
1977:
1953:
1908:
1888:
1865:
1770:
1731:
1711:
1659:
1522:
1502:
1464:
1426:
1406:
1386:
1374:. This can be computed in one of several ways. If
1366:
1346:
1326:
1293:
1232:
1192:
1150:
1130:
1072:
1052:
1032:
1012:
963:
943:
923:
873:
824:
782:
735:
699:
655:
632:
612:
592:
568:
524:
491:
471:
418:
382:
338:
309:
289:
269:
246:
222:
181:
149:
99:
1719:. This calculation produces the original message
3389:
61:in 1985. ElGamal encryption is used in the free
2287:(1998). "The Decision Diffie-Hellman problem".
2101:, one can easily construct a valid encryption
479:. Alice publishes this public key and retains
3026:
2513:
2339:
109:multiplicative group of integers modulo
2422:
2399:
694:
670:
377:
353:
2527:
2395:
2393:
2270:"Chapter 8.4 ElGamal public-key encryption"
1965:(CDH) holds in the underlying cyclic group
885:Note that if one knows both the ciphertext
84:ElGamal encryption can be defined over any
3033:
3019:
2520:
2506:
2406:University of Illinois at Urbana-Champaign
2247:, designer of this and other cryptosystems
2360:
2298:
2283:
243:
219:
2390:
951:, one can easily find the shared secret
512:A second party, Bob, encrypts a message
2349:IEEE Transactions on Information Theory
1963:computational Diffie–Hellman assumption
206:Generate an efficient description of a
14:
3390:
2231:Encryption under ElGamal requires two
2027:ElGamal encryption is unconditionally
1294:{\displaystyle c_{1}^{x}=g^{xy}=h^{y}}
3014:
2501:
2841:Naccache–Stern knapsack cryptosystem
2449:
2031:, and therefore is not secure under
2022:Decisional Diffie–Hellman assumption
1994:decisional Diffie–Hellman assumption
1712:{\displaystyle m:=c_{2}\cdot s^{-1}}
640:using a reversible mapping function.
2081:of some (possibly unknown) message
2035:. For example, given an encryption
1013:{\displaystyle c_{2}\cdot m^{-1}=s}
47:asymmetric key encryption algorithm
24:
2462:Topics in Cryptology — CT-RSA 2001
2261:
1985:, then the encryption function is
297:represent the identity element of
25:
3409:
700:{\displaystyle \{1,\ldots ,q-1\}}
383:{\displaystyle \{1,\ldots ,q-1\}}
197:
3368:
3367:
3040:
2383:(conference version appeared in
2277:Handbook of Applied Cryptography
1920:
164:
2872:Discrete logarithm cryptography
1442:. An alternative is to compute
825:{\displaystyle c_{2}:=m\cdot s}
3229:Information-theoretic security
2416:
2333:
2143:{\displaystyle (c_{1},2c_{2})}
2137:
2108:
2068:
2042:
1896:back to the plaintext message
1826:
1814:
1771:{\displaystyle c_{2}=m\cdot s}
1629:
1615:
1604:
1592:
1436:modular multiplicative inverse
1125:
1099:
918:
892:
868:
842:
563:
539:
532:to Alice under her public key
466:
442:
13:
1:
3398:Public-key encryption schemes
2326:
2215:
2208:. Another proposed scheme is
2204:. Its proof does not use the
2074:{\displaystyle (c_{1},c_{2})}
1131:{\displaystyle (c_{1},c_{2})}
1087:
924:{\displaystyle (c_{1},c_{2})}
874:{\displaystyle (c_{1},c_{2})}
507:
65:software, recent versions of
2887:Non-commutative cryptography
1440:extended Euclidean algorithm
1193:{\displaystyle s:=c_{1}^{x}}
1092:Alice decrypts a ciphertext
783:{\displaystyle c_{1}:=g^{y}}
503:, which must be kept secret.
7:
3345:Message authentication code
3300:Cryptographic hash function
3113:Cryptographic hash function
2984:Identity-based cryptography
2877:Elliptic-curve cryptography
2402:"Elgamal encryption scheme"
2400:Mike Rosulek (2008-12-13).
2238:
1936:
1503:{\displaystyle c_{1}^{q-x}}
1233:{\displaystyle c_{1}=g^{y}}
75:Digital Signature Algorithm
55:Diffie–Hellman key exchange
10:
3414:
3224:Harvest now, decrypt later
1438:can be computed using the
77:(DSA) is a variant of the
29:
3363:
3340:Post-quantum cryptography
3292:
3048:
3010:
2989:Post-quantum cryptography
2946:
2938:Post-Quantum Cryptography
2905:
2864:
2792:
2734:
2615:
2542:
2535:
2497:
2493:
2290:Algorithmic Number Theory
2182:Cramer–Shoup cryptosystem
1510:. This is the inverse of
835:Bob sends the ciphertext
569:{\displaystyle (G,q,g,h)}
472:{\displaystyle (G,q,g,h)}
43:ElGamal encryption system
3330:Quantum key distribution
3320:Authenticated encryption
3175:Random number generation
2470:10.1007/3-540-45353-9_12
2371:10.1109/TIT.1985.1057074
2251:ElGamal signature scheme
2224:, meaning that a single
2033:chosen ciphertext attack
2016:, then ElGamal achieves
736:{\displaystyle s:=h^{y}}
419:{\displaystyle h:=g^{x}}
79:ElGamal signature scheme
32:ElGamal signature scheme
3325:Public-key cryptography
3315:Symmetric-key algorithm
3118:Key derivation function
3078:Cryptographic primitive
3071:Authentication protocol
3061:Outline of cryptography
3056:History of cryptography
2882:Hash-based cryptography
2529:Public-key cryptography
2425:Public Key Cryptography
435:consists of the values
189:, then using this as a
51:public-key cryptography
27:Public-key cryptosystem
3066:Cryptographic protocol
2340:Taher ElGamal (1985).
2256:Homomorphic encryption
2220:ElGamal encryption is
2198:
2167:
2144:
2095:
2075:
2010:
1979:
1955:
1910:
1890:
1867:
1772:
1733:
1713:
1661:
1524:
1504:
1466:
1465:{\displaystyle s^{-1}}
1428:
1408:
1388:
1368:
1348:
1328:
1327:{\displaystyle s^{-1}}
1295:
1234:
1194:
1152:
1132:
1074:
1054:
1034:
1014:
965:
945:
925:
875:
826:
784:
737:
701:
657:
634:
614:
594:
570:
526:
493:
473:
420:
384:
340:
311:
291:
271:
248:
224:
183:
151:
101:
57:. It was described by
53:which is based on the
3219:End-to-end encryption
3165:Cryptojacking malware
2544:Integer factorization
2199:
2168:
2145:
2096:
2076:
2011:
1980:
1956:
1911:
1891:
1868:
1773:
1734:
1714:
1662:
1525:
1505:
1467:
1429:
1409:
1389:
1369:
1349:
1329:
1296:
1235:
1195:
1153:
1138:with her private key
1133:
1075:
1055:
1035:
1015:
966:
946:
926:
876:
827:
785:
743:. This is called the
738:
702:
658:
635:
615:
595:
571:
527:
494:
474:
421:
385:
341:
312:
292:
272:
249:
225:
184:
157:related to computing
152:
102:
3335:Quantum cryptography
3259:Trusted timestamping
2188:
2154:
2105:
2085:
2039:
2000:
1969:
1945:
1900:
1880:
1782:
1743:
1723:
1674:
1538:
1514:
1476:
1446:
1418:
1398:
1378:
1358:
1338:
1308:
1244:
1204:
1166:
1142:
1096:
1064:
1044:
1024:
975:
955:
935:
889:
839:
797:
754:
714:
667:
647:
624:
604:
584:
536:
516:
483:
439:
397:
350:
330:
301:
281:
261:
237:
213:
173:
141:
130:is an odd prime and
91:
3098:Cryptographic nonce
2847:Three-pass protocol
2206:random oracle model
1927:hybrid cryptosystem
1567:
1499:
1261:
1189:
1020:. Therefore, a new
247:{\displaystyle q\,}
223:{\displaystyle G\,}
159:discrete logarithms
3204:Subliminal channel
3188:Pseudorandom noise
3135:Key (cryptography)
2617:Discrete logarithm
2433:10.1007/BFb0054019
2309:10.1007/BFb0054851
2194:
2166:{\displaystyle 2m}
2163:
2140:
2091:
2071:
2006:
1975:
1951:
1906:
1886:
1863:
1768:
1729:
1709:
1657:
1547:
1532:Lagrange's theorem
1520:
1500:
1479:
1462:
1424:
1404:
1384:
1364:
1344:
1324:
1291:
1247:
1230:
1190:
1175:
1148:
1128:
1080:is also called an
1070:
1050:
1030:
1010:
961:
941:
931:and the plaintext
921:
871:
822:
780:
733:
697:
653:
643:Choose an integer
630:
610:
590:
566:
522:
489:
469:
416:
380:
336:
326:Choose an integer
307:
287:
267:
244:
220:
179:
147:
97:
3385:
3384:
3381:
3380:
3264:Key-based routing
3254:Trapdoor function
3125:Digital signature
3006:
3005:
3002:
3001:
2954:Digital signature
2897:Trapdoor function
2860:
2859:
2577:Goldwasser–Micali
2479:978-3-540-41898-6
2442:978-3-540-69105-1
2318:978-3-540-64657-0
2197:{\displaystyle G}
2094:{\displaystyle m}
2018:semantic security
2009:{\displaystyle G}
1978:{\displaystyle G}
1954:{\displaystyle G}
1931:level of security
1909:{\displaystyle M}
1889:{\displaystyle m}
1732:{\displaystyle m}
1523:{\displaystyle s}
1427:{\displaystyle n}
1407:{\displaystyle n}
1387:{\displaystyle G}
1367:{\displaystyle G}
1347:{\displaystyle s}
1334:, the inverse of
1151:{\displaystyle x}
1073:{\displaystyle y}
1053:{\displaystyle s}
1033:{\displaystyle y}
964:{\displaystyle s}
944:{\displaystyle m}
656:{\displaystyle y}
633:{\displaystyle G}
613:{\displaystyle m}
593:{\displaystyle M}
525:{\displaystyle M}
492:{\displaystyle x}
339:{\displaystyle x}
310:{\displaystyle G}
290:{\displaystyle e}
270:{\displaystyle g}
182:{\displaystyle s}
150:{\displaystyle G}
100:{\displaystyle G}
63:GNU Privacy Guard
16:(Redirected from
3405:
3371:
3370:
3199:Insecure channel
3035:
3028:
3021:
3012:
3011:
2843:
2744:
2739:
2699:signature scheme
2602:Okamoto–Uchiyama
2540:
2539:
2522:
2515:
2508:
2499:
2498:
2495:
2494:
2491:
2490:
2484:
2483:
2453:
2447:
2446:
2420:
2414:
2413:
2408:. Archived from
2397:
2388:
2382:
2364:
2346:
2337:
2322:
2302:
2280:
2274:
2203:
2201:
2200:
2195:
2172:
2170:
2169:
2164:
2149:
2147:
2146:
2141:
2136:
2135:
2120:
2119:
2100:
2098:
2097:
2092:
2080:
2078:
2077:
2072:
2067:
2066:
2054:
2053:
2015:
2013:
2012:
2007:
1984:
1982:
1981:
1976:
1960:
1958:
1957:
1952:
1915:
1913:
1912:
1907:
1895:
1893:
1892:
1887:
1872:
1870:
1869:
1864:
1844:
1843:
1810:
1809:
1794:
1793:
1777:
1775:
1774:
1769:
1755:
1754:
1738:
1736:
1735:
1730:
1718:
1716:
1715:
1710:
1708:
1707:
1692:
1691:
1666:
1664:
1663:
1658:
1650:
1649:
1637:
1636:
1627:
1626:
1611:
1610:
1583:
1582:
1566:
1555:
1529:
1527:
1526:
1521:
1509:
1507:
1506:
1501:
1498:
1487:
1471:
1469:
1468:
1463:
1461:
1460:
1433:
1431:
1430:
1425:
1413:
1411:
1410:
1405:
1393:
1391:
1390:
1385:
1373:
1371:
1370:
1365:
1353:
1351:
1350:
1345:
1333:
1331:
1330:
1325:
1323:
1322:
1300:
1298:
1297:
1292:
1290:
1289:
1277:
1276:
1260:
1255:
1239:
1237:
1236:
1231:
1229:
1228:
1216:
1215:
1199:
1197:
1196:
1191:
1188:
1183:
1157:
1155:
1154:
1149:
1137:
1135:
1134:
1129:
1124:
1123:
1111:
1110:
1079:
1077:
1076:
1071:
1059:
1057:
1056:
1051:
1040:and hence a new
1039:
1037:
1036:
1031:
1019:
1017:
1016:
1011:
1003:
1002:
987:
986:
970:
968:
967:
962:
950:
948:
947:
942:
930:
928:
927:
922:
917:
916:
904:
903:
880:
878:
877:
872:
867:
866:
854:
853:
831:
829:
828:
823:
809:
808:
789:
787:
786:
781:
779:
778:
766:
765:
742:
740:
739:
734:
732:
731:
706:
704:
703:
698:
662:
660:
659:
654:
639:
637:
636:
631:
619:
617:
616:
611:
599:
597:
596:
591:
580:Map the message
575:
573:
572:
567:
531:
529:
528:
523:
498:
496:
495:
490:
478:
476:
475:
470:
425:
423:
422:
417:
415:
414:
389:
387:
386:
381:
345:
343:
342:
337:
316:
314:
313:
308:
296:
294:
293:
288:
276:
274:
273:
268:
253:
251:
250:
245:
229:
227:
226:
221:
188:
186:
185:
180:
156:
154:
153:
148:
136:
106:
104:
103:
98:
21:
3413:
3412:
3408:
3407:
3406:
3404:
3403:
3402:
3388:
3387:
3386:
3377:
3359:
3288:
3044:
3039:
2998:
2942:
2906:Standardization
2901:
2856:
2839:
2788:
2736:Lattice/SVP/CVP
2730:
2611:
2557:Blum–Goldwasser
2531:
2526:
2488:
2487:
2480:
2454:
2450:
2443:
2421:
2417:
2398:
2391:
2387:'84, pp. 10–18)
2362:10.1.1.476.4791
2344:
2338:
2334:
2329:
2319:
2300:10.1.1.461.9971
2272:
2264:
2262:Further reading
2241:
2233:exponentiations
2218:
2189:
2186:
2185:
2155:
2152:
2151:
2150:of the message
2131:
2127:
2115:
2111:
2106:
2103:
2102:
2086:
2083:
2082:
2062:
2058:
2049:
2045:
2040:
2037:
2036:
2001:
1998:
1997:
1996:(DDH) holds in
1970:
1967:
1966:
1946:
1943:
1942:
1939:
1923:
1901:
1898:
1897:
1881:
1878:
1877:
1836:
1832:
1802:
1798:
1789:
1785:
1783:
1780:
1779:
1750:
1746:
1744:
1741:
1740:
1724:
1721:
1720:
1700:
1696:
1687:
1683:
1675:
1672:
1671:
1645:
1641:
1632:
1628:
1622:
1618:
1591:
1587:
1575:
1571:
1556:
1551:
1539:
1536:
1535:
1515:
1512:
1511:
1488:
1483:
1477:
1474:
1473:
1453:
1449:
1447:
1444:
1443:
1419:
1416:
1415:
1399:
1396:
1395:
1379:
1376:
1375:
1359:
1356:
1355:
1339:
1336:
1335:
1315:
1311:
1309:
1306:
1305:
1285:
1281:
1269:
1265:
1256:
1251:
1245:
1242:
1241:
1224:
1220:
1211:
1207:
1205:
1202:
1201:
1184:
1179:
1167:
1164:
1163:
1143:
1140:
1139:
1119:
1115:
1106:
1102:
1097:
1094:
1093:
1090:
1065:
1062:
1061:
1045:
1042:
1041:
1025:
1022:
1021:
995:
991:
982:
978:
976:
973:
972:
956:
953:
952:
936:
933:
932:
912:
908:
899:
895:
890:
887:
886:
862:
858:
849:
845:
840:
837:
836:
804:
800:
798:
795:
794:
774:
770:
761:
757:
755:
752:
751:
727:
723:
715:
712:
711:
668:
665:
664:
648:
645:
644:
625:
622:
621:
605:
602:
601:
585:
582:
581:
537:
534:
533:
517:
514:
513:
510:
484:
481:
480:
440:
437:
436:
410:
406:
398:
395:
394:
351:
348:
347:
331:
328:
327:
302:
299:
298:
282:
279:
278:
262:
259:
258:
238:
235:
234:
214:
211:
210:
200:
174:
171:
170:
167:
142:
139:
138:
131:
114:if and only if
92:
89:
88:
35:
28:
23:
22:
15:
12:
11:
5:
3411:
3401:
3400:
3383:
3382:
3379:
3378:
3376:
3375:
3364:
3361:
3360:
3358:
3357:
3352:
3350:Random numbers
3347:
3342:
3337:
3332:
3327:
3322:
3317:
3312:
3307:
3302:
3296:
3294:
3290:
3289:
3287:
3286:
3281:
3276:
3274:Garlic routing
3271:
3266:
3261:
3256:
3251:
3246:
3241:
3236:
3231:
3226:
3221:
3216:
3211:
3206:
3201:
3196:
3194:Secure channel
3191:
3185:
3184:
3183:
3172:
3167:
3162:
3157:
3155:Key stretching
3152:
3147:
3142:
3137:
3132:
3127:
3122:
3121:
3120:
3115:
3105:
3103:Cryptovirology
3100:
3095:
3090:
3088:Cryptocurrency
3085:
3080:
3075:
3074:
3073:
3063:
3058:
3052:
3050:
3046:
3045:
3038:
3037:
3030:
3023:
3015:
3008:
3007:
3004:
3003:
3000:
2999:
2997:
2996:
2991:
2986:
2981:
2976:
2971:
2966:
2961:
2956:
2950:
2948:
2944:
2943:
2941:
2940:
2935:
2930:
2925:
2920:
2915:
2909:
2907:
2903:
2902:
2900:
2899:
2894:
2889:
2884:
2879:
2874:
2868:
2866:
2862:
2861:
2858:
2857:
2855:
2854:
2849:
2844:
2837:
2835:Merkle–Hellman
2832:
2827:
2822:
2817:
2812:
2807:
2802:
2796:
2794:
2790:
2789:
2787:
2786:
2781:
2776:
2771:
2766:
2761:
2756:
2750:
2748:
2732:
2731:
2729:
2728:
2723:
2718:
2713:
2708:
2703:
2702:
2701:
2691:
2686:
2681:
2680:
2679:
2674:
2664:
2659:
2658:
2657:
2652:
2642:
2637:
2632:
2627:
2621:
2619:
2613:
2612:
2610:
2609:
2604:
2599:
2594:
2589:
2584:
2582:Naccache–Stern
2579:
2574:
2569:
2564:
2559:
2554:
2548:
2546:
2537:
2533:
2532:
2525:
2524:
2517:
2510:
2502:
2486:
2485:
2478:
2448:
2441:
2415:
2412:on 2016-07-22.
2389:
2355:(4): 469–472.
2331:
2330:
2328:
2325:
2324:
2323:
2317:
2281:
2263:
2260:
2259:
2258:
2253:
2248:
2240:
2237:
2217:
2214:
2193:
2162:
2159:
2139:
2134:
2130:
2126:
2123:
2118:
2114:
2110:
2090:
2070:
2065:
2061:
2057:
2052:
2048:
2044:
2005:
1974:
1950:
1938:
1935:
1922:
1919:
1918:
1917:
1905:
1885:
1874:
1862:
1859:
1856:
1853:
1850:
1847:
1842:
1839:
1835:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1808:
1805:
1801:
1797:
1792:
1788:
1767:
1764:
1761:
1758:
1753:
1749:
1728:
1706:
1703:
1699:
1695:
1690:
1686:
1682:
1679:
1668:
1656:
1653:
1648:
1644:
1640:
1635:
1631:
1625:
1621:
1617:
1614:
1609:
1606:
1603:
1600:
1597:
1594:
1590:
1586:
1581:
1578:
1574:
1570:
1565:
1562:
1559:
1554:
1550:
1546:
1543:
1519:
1497:
1494:
1491:
1486:
1482:
1459:
1456:
1452:
1434:is prime, the
1423:
1403:
1383:
1363:
1343:
1321:
1318:
1314:
1302:
1288:
1284:
1280:
1275:
1272:
1268:
1264:
1259:
1254:
1250:
1227:
1223:
1219:
1214:
1210:
1187:
1182:
1178:
1174:
1171:
1147:
1127:
1122:
1118:
1114:
1109:
1105:
1101:
1089:
1086:
1069:
1049:
1029:
1009:
1006:
1001:
998:
994:
990:
985:
981:
960:
940:
920:
915:
911:
907:
902:
898:
894:
883:
882:
870:
865:
861:
857:
852:
848:
844:
833:
821:
818:
815:
812:
807:
803:
791:
777:
773:
769:
764:
760:
748:
730:
726:
722:
719:
708:
696:
693:
690:
687:
684:
681:
678:
675:
672:
663:randomly from
652:
641:
629:
609:
600:to an element
589:
565:
562:
559:
556:
553:
550:
547:
544:
541:
521:
509:
506:
505:
504:
488:
468:
465:
462:
459:
456:
453:
450:
447:
444:
427:
413:
409:
405:
402:
391:
379:
376:
373:
370:
367:
364:
361:
358:
355:
346:randomly from
335:
324:
323:
322:
306:
286:
266:
242:
218:
199:
198:Key generation
196:
178:
166:
163:
146:
96:
26:
9:
6:
4:
3:
2:
3410:
3399:
3396:
3395:
3393:
3374:
3366:
3365:
3362:
3356:
3355:Steganography
3353:
3351:
3348:
3346:
3343:
3341:
3338:
3336:
3333:
3331:
3328:
3326:
3323:
3321:
3318:
3316:
3313:
3311:
3310:Stream cipher
3308:
3306:
3303:
3301:
3298:
3297:
3295:
3291:
3285:
3282:
3280:
3277:
3275:
3272:
3270:
3269:Onion routing
3267:
3265:
3262:
3260:
3257:
3255:
3252:
3250:
3249:Shared secret
3247:
3245:
3242:
3240:
3237:
3235:
3232:
3230:
3227:
3225:
3222:
3220:
3217:
3215:
3212:
3210:
3207:
3205:
3202:
3200:
3197:
3195:
3192:
3189:
3186:
3181:
3178:
3177:
3176:
3173:
3171:
3168:
3166:
3163:
3161:
3158:
3156:
3153:
3151:
3148:
3146:
3145:Key generator
3143:
3141:
3138:
3136:
3133:
3131:
3128:
3126:
3123:
3119:
3116:
3114:
3111:
3110:
3109:
3108:Hash function
3106:
3104:
3101:
3099:
3096:
3094:
3091:
3089:
3086:
3084:
3083:Cryptanalysis
3081:
3079:
3076:
3072:
3069:
3068:
3067:
3064:
3062:
3059:
3057:
3054:
3053:
3051:
3047:
3043:
3036:
3031:
3029:
3024:
3022:
3017:
3016:
3013:
3009:
2995:
2992:
2990:
2987:
2985:
2982:
2980:
2977:
2975:
2972:
2970:
2967:
2965:
2962:
2960:
2957:
2955:
2952:
2951:
2949:
2945:
2939:
2936:
2934:
2931:
2929:
2926:
2924:
2921:
2919:
2916:
2914:
2911:
2910:
2908:
2904:
2898:
2895:
2893:
2890:
2888:
2885:
2883:
2880:
2878:
2875:
2873:
2870:
2869:
2867:
2863:
2853:
2850:
2848:
2845:
2842:
2838:
2836:
2833:
2831:
2828:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2806:
2803:
2801:
2798:
2797:
2795:
2791:
2785:
2782:
2780:
2777:
2775:
2772:
2770:
2767:
2765:
2762:
2760:
2757:
2755:
2752:
2751:
2749:
2747:
2742:
2737:
2733:
2727:
2724:
2722:
2719:
2717:
2714:
2712:
2709:
2707:
2704:
2700:
2697:
2696:
2695:
2692:
2690:
2687:
2685:
2682:
2678:
2675:
2673:
2670:
2669:
2668:
2665:
2663:
2660:
2656:
2653:
2651:
2648:
2647:
2646:
2643:
2641:
2638:
2636:
2633:
2631:
2628:
2626:
2623:
2622:
2620:
2618:
2614:
2608:
2607:Schmidt–Samoa
2605:
2603:
2600:
2598:
2595:
2593:
2590:
2588:
2585:
2583:
2580:
2578:
2575:
2573:
2570:
2568:
2567:Damgård–Jurik
2565:
2563:
2562:Cayley–Purser
2560:
2558:
2555:
2553:
2550:
2549:
2547:
2545:
2541:
2538:
2534:
2530:
2523:
2518:
2516:
2511:
2509:
2504:
2503:
2500:
2496:
2492:
2481:
2475:
2471:
2467:
2463:
2459:
2452:
2444:
2438:
2434:
2430:
2426:
2419:
2411:
2407:
2403:
2396:
2394:
2386:
2380:
2376:
2372:
2368:
2363:
2358:
2354:
2350:
2343:
2336:
2332:
2320:
2314:
2310:
2306:
2301:
2296:
2292:
2291:
2286:
2282:
2278:
2271:
2266:
2265:
2257:
2254:
2252:
2249:
2246:
2245:Taher Elgamal
2243:
2242:
2236:
2234:
2229:
2227:
2223:
2222:probabilistic
2213:
2211:
2207:
2191:
2183:
2178:
2174:
2160:
2157:
2132:
2128:
2124:
2121:
2116:
2112:
2088:
2063:
2059:
2055:
2050:
2046:
2034:
2030:
2025:
2023:
2019:
2003:
1995:
1990:
1988:
1972:
1964:
1948:
1934:
1932:
1928:
1921:Practical use
1903:
1883:
1875:
1860:
1857:
1854:
1851:
1848:
1845:
1840:
1837:
1833:
1829:
1823:
1820:
1817:
1811:
1806:
1803:
1799:
1795:
1790:
1786:
1765:
1762:
1759:
1756:
1751:
1747:
1726:
1704:
1701:
1697:
1693:
1688:
1684:
1680:
1677:
1669:
1654:
1651:
1646:
1642:
1638:
1633:
1623:
1619:
1612:
1607:
1601:
1598:
1595:
1588:
1584:
1579:
1576:
1572:
1568:
1563:
1560:
1557:
1552:
1548:
1544:
1541:
1533:
1517:
1495:
1492:
1489:
1484:
1480:
1457:
1454:
1450:
1441:
1437:
1421:
1401:
1381:
1361:
1354:in the group
1341:
1319:
1316:
1312:
1303:
1286:
1282:
1278:
1273:
1270:
1266:
1262:
1257:
1252:
1248:
1225:
1221:
1217:
1212:
1208:
1185:
1180:
1176:
1172:
1169:
1161:
1160:
1159:
1145:
1120:
1116:
1112:
1107:
1103:
1085:
1083:
1082:ephemeral key
1067:
1047:
1027:
1007:
1004:
999:
996:
992:
988:
983:
979:
958:
938:
913:
909:
905:
900:
896:
863:
859:
855:
850:
846:
834:
819:
816:
813:
810:
805:
801:
792:
775:
771:
767:
762:
758:
749:
746:
745:shared secret
728:
724:
720:
717:
709:
691:
688:
685:
682:
679:
676:
673:
650:
642:
627:
607:
587:
579:
578:
577:
560:
557:
554:
551:
548:
545:
542:
519:
502:
486:
463:
460:
457:
454:
451:
448:
445:
434:
433:
428:
411:
407:
403:
400:
392:
374:
371:
368:
365:
362:
359:
356:
333:
325:
319:
318:
304:
284:
264:
257:
240:
233:
216:
209:
205:
204:
203:
195:
192:
176:
165:The algorithm
162:
160:
144:
134:
129:
125:
121:
117:
113:
112:
94:
87:
82:
80:
76:
72:
71:cryptosystems
68:
64:
60:
59:Taher Elgamal
56:
52:
48:
44:
40:
33:
19:
3305:Block cipher
3150:Key schedule
3140:Key exchange
3130:Kleptography
3093:Cryptosystem
3042:Cryptography
2994:OpenPGP card
2974:Web of trust
2693:
2630:Cramer–Shoup
2461:
2451:
2424:
2418:
2410:the original
2352:
2348:
2335:
2289:
2279:. CRC Press.
2276:
2230:
2219:
2179:
2175:
2026:
1991:
1940:
1924:
1158:as follows:
1091:
884:
744:
576:as follows:
511:
500:
430:
208:cyclic group
201:
191:one-time pad
168:
132:
127:
123:
119:
118:is 1, 2, 4,
115:
110:
86:cyclic group
83:
69:, and other
42:
39:cryptography
36:
3293:Mathematics
3284:Mix network
2964:Fingerprint
2928:NSA Suite B
2892:RSA problem
2769:NTRUEncrypt
1530:because of
501:private key
3244:Ciphertext
3214:Decryption
3209:Encryption
3170:Ransomware
2918:IEEE P1363
2536:Algorithms
2327:References
2216:Efficiency
1739:, because
1088:Decryption
508:Encryption
432:public key
3234:Plaintext
2357:CiteSeerX
2295:CiteSeerX
2285:Dan Boneh
2226:plaintext
2029:malleable
1852:⋅
1838:−
1830:⋅
1821:⋅
1804:−
1796:⋅
1763:⋅
1702:−
1694:⋅
1599:−
1585:⋅
1561:−
1545:⋅
1493:−
1455:−
1317:−
997:−
989:⋅
881:to Alice.
817:⋅
689:−
680:…
372:−
363:…
256:generator
3392:Category
3373:Category
3279:Kademlia
3239:Codetext
3182:(CSPRNG)
2979:Key size
2913:CRYPTREC
2830:McEliece
2784:RLWE-SIG
2779:RLWE-KEX
2774:NTRUSign
2587:Paillier
2239:See also
1937:Security
1778:; hence
1670:Compute
1534:, since
1414:, where
1304:Compute
1200:. Since
1162:Compute
971:, since
793:Compute
750:Compute
710:Compute
393:Compute
126:, where
18:El Gamal
3049:General
2825:Lamport
2805:CEILIDH
2764:NewHope
2711:Schnorr
2694:ElGamal
2672:Ed25519
2552:Benaloh
2379:2973271
1992:If the
1987:one-way
499:as her
277:. Let
107:, like
3160:Keygen
2947:Topics
2923:NESSIE
2865:Theory
2793:Others
2650:X25519
2476:
2439:
2385:CRYPTO
2377:
2359:
2315:
2297:
135:> 0
73:. The
45:is an
41:, the
3190:(PRN)
2759:Kyber
2754:BLISS
2716:SPEKE
2684:ECMQV
2677:Ed448
2667:EdDSA
2662:ECDSA
2592:Rabin
2375:S2CID
2345:(PDF)
2273:(PDF)
2210:DHIES
254:with
232:order
2959:OAEP
2933:CNSA
2810:EPOC
2655:X448
2645:ECDH
2474:ISBN
2437:ISBN
2313:ISBN
1876:Map
429:The
321:use.
122:or 2
49:for
2969:PKI
2852:XTR
2820:IES
2815:HFE
2746:SIS
2741:LWE
2726:STS
2721:SRP
2706:MQV
2689:EKE
2640:DSA
2625:BLS
2597:RSA
2572:GMR
2466:doi
2429:doi
2367:doi
2305:doi
1472:as
620:of
230:of
67:PGP
37:In
3394::
2800:AE
2635:DH
2472:.
2460:.
2435:.
2404:.
2392:^
2373:.
2365:.
2353:31
2351:.
2347:.
2311:.
2303:.
2275:.
2173:.
1989:.
1681::=
1240:,
1173::=
1084:.
811::=
768::=
721::=
404::=
317:.
161:.
3034:e
3027:t
3020:v
2743:/
2738:/
2521:e
2514:t
2507:v
2482:.
2468::
2445:.
2431::
2381:.
2369::
2321:.
2307::
2192:G
2161:m
2158:2
2138:)
2133:2
2129:c
2125:2
2122:,
2117:1
2113:c
2109:(
2089:m
2069:)
2064:2
2060:c
2056:,
2051:1
2047:c
2043:(
2004:G
1973:G
1949:G
1916:.
1904:M
1884:m
1873:.
1861:m
1858:=
1855:e
1849:m
1846:=
1841:1
1834:s
1827:)
1824:s
1818:m
1815:(
1812:=
1807:1
1800:s
1791:2
1787:c
1766:s
1760:m
1757:=
1752:2
1748:c
1727:m
1705:1
1698:s
1689:2
1685:c
1678:m
1667:.
1655:e
1652:=
1647:y
1643:e
1639:=
1634:y
1630:)
1624:q
1620:g
1616:(
1613:=
1608:y
1605:)
1602:x
1596:q
1593:(
1589:g
1580:y
1577:x
1573:g
1569:=
1564:x
1558:q
1553:1
1549:c
1542:s
1518:s
1496:x
1490:q
1485:1
1481:c
1458:1
1451:s
1422:n
1402:n
1382:G
1362:G
1342:s
1320:1
1313:s
1287:y
1283:h
1279:=
1274:y
1271:x
1267:g
1263:=
1258:x
1253:1
1249:c
1226:y
1222:g
1218:=
1213:1
1209:c
1186:x
1181:1
1177:c
1170:s
1146:x
1126:)
1121:2
1117:c
1113:,
1108:1
1104:c
1100:(
1068:y
1048:s
1028:y
1008:s
1005:=
1000:1
993:m
984:2
980:c
959:s
939:m
919:)
914:2
910:c
906:,
901:1
897:c
893:(
869:)
864:2
860:c
856:,
851:1
847:c
843:(
832:.
820:s
814:m
806:2
802:c
790:.
776:y
772:g
763:1
759:c
747:.
729:y
725:h
718:s
707:.
695:}
692:1
686:q
683:,
677:,
674:1
671:{
651:y
628:G
608:m
588:M
564:)
561:h
558:,
555:g
552:,
549:q
546:,
543:G
540:(
520:M
487:x
467:)
464:h
461:,
458:g
455:,
452:q
449:,
446:G
443:(
426:.
412:x
408:g
401:h
390:.
378:}
375:1
369:q
366:,
360:,
357:1
354:{
334:x
305:G
285:e
265:g
241:q
217:G
177:s
145:G
133:k
128:p
124:p
120:p
116:n
111:n
95:G
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.