苦戦した。ちゃんと考えたら分かったが、$d = \frac{p - 1}{2}$でよいというのは私にはまだ自明でなかった。

problem

素数$p$と$g, A$が公開されている。鍵$d$と平文$m$が隠されていて、$B \equiv g^d \pmod{p}$と$k \equiv A^d \pmod{p}$と$c \equiv km \pmod{p}$があり、このうち$B, c$が与えられる。$m$を求めろ。

solution

$B \equiv -1 \pmod{p}$が比較により分かる。 つまり$g^d \equiv -1 \pmod{p}$である。 これは離散対数問題であるが、$\forall a \not\equiv 0. a^n \equiv 1 \pmod{p}$と$p-1 \mid n$が同値であることが示せるので$d = \frac{p - 1}{2}$。 この同値性について、逆方向はFermatの小定理、順方向はLagrangeの定理の系(有限群の元の位数は群の位数の約数)と$(\mathbb{Z}/p\mathbb{Z})^{\times}$が巡回群であること(あるいは原始根の存在性)から示せる。

implementation

#!/usr/bin/env python3

p = 1044388881413152506679602719846529545831269060992135009022588756444338172022322690710444046669809783930111585737890362691860127079270495454517218673016928427459146001866885779762982229321192368303346235204368051010309155674155697460347176946394076535157284994895284821633700921811716738972451834979455897010306333468590751358365138782250372269117968985194322444535687415522007151638638141456178420621277822674995027990278673458629544391736919766299005511505446177668154446234882665961680796576903199116089347634947187778906528008004756692571666922964122566174582776707332452371001272163776841229318324903125740713574141005124561965913888899753461735347970011693256316751660678950830027510255804846105583465055446615090444309583050775808509297040039680057435342253926566240898195863631588888936364129920059308455669454034010391478238784189888594672336242763795138176353222845524644040094258962433613354036104643881925238489224010194193088911666165584229424668165441688927790460608264864204237717002054744337988941974661214699689706521543006262604535890998125752275942608772174376107314217749233048217904944409836238235772306749874396760463376480215133461333478395682746608242585133953883882226786118030184028136755970045385534758453247
g = 5
A = 1026312539297800437474663698165859314949881437729617621666434357798219198741950468733395500361477359726152747087790103309627020498122003777642051150130697457594304849673838709900017711265818285080832347734747895550397950729716624922572654209637755195129162139245110756558638081495998280747642920484467428206475906559638681536868548289456924005274209311355030582255692087426910634838198143851507435754029135363794578075936092774722678311786272841489629294721103591751528609388061794369341067986401129462942050916582521451289187645626081017578576190303952351748434876686541368607656026867091583868645619423975306245327421218767449273192101105293424028461698783545171866070124432565063559495566733441286372612161876492134408160732339966921175762866198980795890946054558528891296203285979664329713156129091098226212735763844909789916934266711879564086741733061623347281499025678164709559814150194881622611023214199434022258730549350019749882889143749385314934896284396513061241138504029046053964944026179039768718830854958634216721133676746317913559932277050177463811150719675119168868527853864167729206220819613297736800799391257602899169041109002518019207734013899840092155297682096290489330476118066934735827328128343402508975429994312

with open('ciphertext.txt') as fh:
    B = int(fh.readline())
    c = int(fh.readline())

assert B == p - 1
assert pow(B, 2, p) == 1

import gmpy2
d = (p - 1) // 2
assert pow(g, d, p) == B
k = pow(A, d, p)
m = c * gmpy2.invert(k, p) % p
print(int(m).to_bytes(512, 'big'))
  • 2017年 10月 22日 日曜日 12:38:14 JST
    • p-1 \mid n のつもりで n \mod p-1 って書いてたので修正
  • 2017年 10月 23日 月曜日 17:31:40 JST
    • 略証など加えて修正