Hatena Blog Tags
はてなブログ トップ
ElGamal暗号
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

ElGamal暗号

(サイエンス)
【えるがまるあんごう】

1982年にElGamalが考案した公開鍵暗号。

方式

鍵生成

  1. 大きな素数pを選ぶ
  2. 位数がpの巡回群Gの生成元gを選ぶ
  3. xを\{1,2,...,p-1\}からランダムに選ぶ
  4. yをy=g^xとする

公開鍵は(p,g,y)。秘密鍵はx。

暗号化

m \in Gを暗号化する。

  1. kをZ_{p-1}からランダムに選ぶ
  2. c_1 = g^k とする
  3. c_2 = m y^kとする

暗号文は(c_1, c_2)。

復号

(c_1, c_2) \in G \times Gを復号する。

  1. m = c_2 ({c_1}^{-1})^xを計算する

楕円曲線について

巡回群Gとして楕円曲線で定義される素数位数の巡回群を選ぶ場合がある。この場合、楕円曲線ElGamalと呼ばれる(→楕円曲線暗号, ECC)。

安全性

直感的に言えば、c_1によってDiffie-Hellman鍵交換を行い、その鍵を用いて平文mをマスクしている。
暗号解読はCDH問題(Computational Diffie-Hellman問題)と等価である*1。CDH問題とは位数が素数pの群Gとその生成元g, g^a, g^bを入力として, g^{ab}を計算する問題。


*リスト：リスト::数学関連

*1:暗号を解読できればCDH問題が解けるし、CDH問題が解ければ暗号を解読できる

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
kdnakt blog•2ヶ月前

今週気になったTLS関連のニュース

2024年2月26日～2024年3月3日に読んだ中で気になったニュースとメモ書きです。社内勉強会TLSらじお第146回分。 [Large Record Sizes for TLS & DTLS] [Cryptography & Security Newsletter #110] [その他のニュース] ▼WindowsのCTLM policy ▼ひとくちPKI 64 ▼chrome.security ▼TLS Trust Expressions解説 [暗認本：45 準同型暗号] [まとめ]

関連ブログ

crypto-writeup-public•4ヶ月前

楕円ElGamal暗号

ElGamal暗号 楕円離散対数問題を利用した暗号 楕円曲線上の点Pとある整数xから Q = xP を計算する。 公開鍵 秘密鍵 暗号化 乱数を持ってきて 復号

crypto-writeup-public•5ヶ月前

Ballare-Micali OT

1-out-of-n Oblivious Transferを構成するプロトコル。すなわち、n個のメッセージを送信し、受信者はそのうち1つだけを受信するが、送信者には、受信者がどれを受信したかわからない 準備 素数位数pを持つ巡回群 のgenerator である、何かしらのハッシュ、SHA1とかでいい のある元 プロトコル Alice から Bob にメッセージを送る Alice は 平文 を持ち、 Bob は と を持つ。 または のどちらかがBobに受信される Bob は を計算した後、 をAliceに送る。Aliceは となっていることを確かめておく Aliceは次の を計算してBobに送…

crypto-writeup-public•5ヶ月前

TokyoWesterns CTF 6th 2020 | The Melancholy of Alice

from Crypto.Util.number import getStrongPrime, getRandomRange N = 1024 def generateKey(): p = getStrongPrime(N) q = (p - 1) // 2 x = getRandomRange(2, q) g = 2 h = pow(g, x, p) pk = (p, q, g, h) sk = x return (pk, sk) def encrypt(m, pk): (p, q, g, h) = pk r = getRandomRange(2, q) c1 = pow(g, r, p) c…

crypto-writeup-public•5ヶ月前

ASIS CTF Finals 2021 | mDLP

#asisctffinals2021 #!/usr/bin/env sage from sage.all import * from Crypto.Util.number import * from secret import gen_prime, gen_base_matrix, flag def keygen(nbit, l): # ## Create the n-bit prime and base square matrix of size l over Ring Z_p # p = gen_prime(nbit) A = gen_base_matrix(p, l) d = randi…

crypto-writeup-public•5ヶ月前

Imaginary CTF 2021 | lines

#imaginaryctf2021 from Crypto.Util.number import bytes_to_long import random flag = bytes_to_long(open("flag.txt", "rb").read()) msg = bytes_to_long(b":roocursion:") p = 82820875767540480278499859101602250644399117699549694231796720388646919033627 g = 2 a = random.randint(0, p) b = random.randint(0,…

crypto-writeup-public•5ヶ月前

Elgamal署名

ElGamal暗号を用いた署名。劣化DSAという感じ 鍵 として公開鍵、秘密鍵 署名 where として署名 検証 が と等しいかをみる

よっちんのブログ•10ヶ月前

UIUCTF 2023 Writeup

この大会は2023/7/1 9:00(JST)～2023/7/3 9:00(JST)に開催されました。 今回もチームで参戦。結果は351点で818チーム中255位でした。 自分で解けた問題をWriteupとして書いておきます。 Join our Discord (misc) Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。 uiuctf{new_era_of_CTFing} Finding Artifacts 1 (osint) Googleで「New York City "Excellent One" bronze statue muse…