[Cryptography] PGP -- Can someone help me understand something?

[Benjamin Kreuter]

On Thu, 2018-08-09 at 06:45 +0000, Matt Maxson wrote:
> List,
> 
> This is a really basic question, but I'm posting it here because I
> don't know where else to start.  I'll welcome any sort of help, but
> certainly don't mind links to articles or someone telling me to go
> google this or that term.  I don't know enough to even start
> searching.
> 
> It begins with this post I recently saw on the Proton Mail reddit:  
> https://www.reddit.com/r/ProtonMail/comments/95jmb5/question_about_export/
> 
> The question was, basically, if someone has access to both a PGP
> encrypted email and a plain text version of the same email, can an
> attacker determine the key.  The answer given was "no".
> 
> I don't understand.  Why can't that happen?

Strictly speaking, the private key could be computed, but the amount of
time required would be so large that nobody needs to worry about it.

Here is a straightforward example using (textbook) ElGamal encryption:

Message:  M
Ciphertext:  (g^r mod P, M g^(r X) mod P)
Secret Key:  X

Clearly it is possible to find X if you know M and the ciphertext, but
doing so would require inverting a discrete logarithm.  The best known
algorithm for doing so runs in O(2^(cuberoot(N))) time, where N is the
size of the modulus P.  So by choosing P to be large (around 3072 bits)
and of the right form (e.g. P = 2 Q + 1 with P, Q both prime), we can
ensure that it would take a longer period of time than any of us need
to worry about.

>   For example, if I have 10 + x = 50  (this can be replaced with any
> formula that has exactly one unknown), I can solve for X.  In my
> thinking, isn't the unknown in the equation simply the key?  Sure,
> the maths are more complex, but it should be a trivial issue to work
> backwards and solve for the key.

The amount of work is not trivial.  If you do not believe me, you can
try it yourself; here are some numbers to work with (sorry for the bad
formatting; everything is base 10):

P:
13926363996276065558692468330773199060524555696443710334960781449106379
659212159
89998533962851551147889762333394954686759784154608590790520937381464710
381150333
02004973156772523098735169139286759121275073881572911959402721877308070
143046178
82305565779560253218389293326255476571809851505638441334921113042853410
476939973
14285773232246498684793510120996180270557561723719251483497402959666522
456665553
28926888106199276298918145333411904301309940457711520289991752982752157
075084267
12029842622209052532302002059137979044295146956655863294220585176569054
072739401
01814029679215812862418250187983055652715790024037003684069569496313683
014762128
76202288464372615103153442690586873738767050431998921594529867287315621
436956992
80889439869067477749476159627276773092512466374979708871987444396593570
978791714
61446630237603696992656461831394041305702306138897009964777489584043165
475060701
462753306518436627034651387393232294450823169

G:
25383118432195766461633265531663857183051561261249840135313282862765653
961099392
61428860825206130760111482424500533156399002140683016219432449689475787
218349122
38624396011289955831629831684607026595932305983372069226133338086940571
756292453
49055319911557863681103288876155003298545700506061394379005016842107346
759098818
28325148212075513947878612186617624094736867062638846427459488577664999
654546886
81987101883364105021354811656616262789664377193370002935646466773821844
181665366
97116948465589430910414907375071422840177810601333410989236534747898910
603549305
47269716503692484342956476310550392624484271690893885876180986878506601
640985024
86323928140689637153658112620773345922256205689260631549892039371982923
953945964
64560016846450593162832942136935500881485608582690926416891193749689347
804403395
60189975737870501472002739359295460930542855514187856097909703001001651
694197222
66323563067452740009759414108448948721611440

G^R:
20198458153576440056821697043105122492455515612498882725923024706816740
551532566
33416439198200487394590173570084700768237058344678063069859333601974265
386631253
77863679796656884855611203236599804364922442517375823791034311256518067
503835936
41195105748405389045817911466018300995760732192395721911364187878462846
110937386
20974624302421587066338480723588722146560464678810225746811309119864128
288236017
16518289135021011314739792453933674449444549086818360437401344266546283
718538711
20780241132605115068693610859319317972395978546881794493247157127046097
740931741
78192799419817944392812069238042461298335149617684543389878345702468821
932787082
06759902860497139659206397603220284603677986000522520647884540748799110
901482881
86257520404250171285950850139226954048490820024741598324806622261986801
986936953
26015056540712551543531045424582357480788882202543091485147057058476229
457818827
39989001989980485371885614223747220113258876

G^XR:
82980372892485241827359730824528445999769522836270373281995696479483050
014051723
65335513744296406884686501876663595185639562944607635629822059208163762
527502524
06267756493121214492012293765100801565011762825211699715626931972235300
060448007
05603323689204591550883230239220920266067898485365739403498266507474848
760475459
01359182200073531664181984847794085088943582352422396221053683534596713
959662659
09033451300316149496455976202915681470409823456748180530014013227148106
251621828
21253863042237523701896039121148913172971825706448432214201022033012660
759113411
34128367493076157994908130047182941334104202352834208949620806679018257
573079338
61134703451079335366844964471250063325264214480556025103616079505802980
221053757
30770429312428441801301145665998194787226075233074050131809147003697362
317140749
87195477080210316821383610416478804273390579720906174575994290253831415
399803109
57926951661706385735085647522726387259694499

This is an encryption of the message '1'.  Find X.

-- Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180809/bf75ad7f/attachment.sig>