Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

ignore 02725.73 - checksum in GnuPG secret key

1 view
Skip to first unread message

Marcel Logen

unread,
Apr 25, 2022, 6:58:30 PM4/25/22
to
Als ich kürzlich noch mal meinen unverschlüsselten RSA3072-Test-
und Analyse-Key ausgegraben habe, stellte ich fest, daß dort im
secret key eine checksum angegeben ist.

| t20$ gpg --show-key rsa-testkeygpg.gpg
| sec rsa3072 2021-09-14 [SC] [expired: 2021-09-30]
| 2C1018709195D978A9F2D5FE16B218085F19B4DA
| uid Marcel Logen (RSA-Testkey) <33320000...@ybtra.de>
|
| t20$

| t20$ gpg --list-packets rsa-testkeygpg.gpg
| # off=0 ctb=95 tag=5 hlen=3 plen=1368
| :secret key packet:
| version 4, algo 1, created 1631615616, expires 0
| pkey[0]: [3072 bits]
| pkey[1]: [17 bits]
| skey[2]: [3068 bits]
| skey[3]: [1536 bits]
| skey[4]: [1536 bits]
| skey[5]: [1535 bits]
| checksum: e692
^^^^^^^^^^^^^^
| keyid: 16B218085F19B4DA
| # off=1371 ctb=b4 tag=13 hlen=2 plen=55
| :user ID packet: "Marcel Logen (RSA-Testkey) <33320000...@ybtra.de>"
| # off=1428 ctb=89 tag=2 hlen=3 plen=468
| :signature packet: algo 1, keyid 16B218085F19B4DA
| version 4, created 1631615616, md5len 0, sigclass 0x13
| digest algo 8, begin of digest 75 c4
| hashed subpkt 33 len 21 (issuer fpr v4 2C1018709195D978A9F2D5FE16B218085F19B4DA)
| hashed subpkt 2 len 4 (sig created 2021-09-14)
| hashed subpkt 27 len 1 (key flags: 03)
| hashed subpkt 9 len 4 (key expires after 16d0h0m)
| hashed subpkt 11 len 4 (pref-sym-algos: 9 8 7 2)
| hashed subpkt 21 len 5 (pref-hash-algos: 10 9 8 11 2)
| hashed subpkt 22 len 3 (pref-zip-algos: 2 3 1)
| hashed subpkt 30 len 1 (features: 01)
| hashed subpkt 23 len 1 (keyserver preferences: 80)
| subpkt 16 len 8 (issuer key ID 16B218085F19B4DA)
| data: [3072 bits]
| t20$

Oder, mit den public und secret Key-Daten:

| t20$ gpg --verbose --list-packets rsa-testkeygpg.gpg | head -n 13 | sed -e 's/^\(.\{90\}\).*\(.\{8\}\)$/\1[...]\2/'
| # off=0 ctb=95 tag=5 hlen=3 plen=1368
| :secret key packet:
| version 4, algo 1, created 1631615616, expires 0
| pkey[0]: C0B4122C2CEDB60A44822B8073A0DC2170754A32869B0C50610AF68FE48CD43F0F7B2497CEE8FACE[...]760B16A9
| pkey[1]: 010001
| skey[2]: 0AD9D8F01DDE36284BDA9C97D0C057C4EB9A89D6B5D7ADE62A20BE3E34B0C2BED8F5FBDB2F2E7FF8[...]32803455
| skey[3]: D4CE8501AF0ABFE60A82B15E4F6DC17E15B6CF3BD5A5B68E796FCE396DDF6B6CA614277BBF4C8EF5[...]892F802B
| skey[4]: E7D0FAA5E681C4C17140B2610C1ECB789561EF9DB1892708F389B86057640398342F8FB2ABF2790D[...]DA66867B
| skey[5]: 4D0217CBF1629164C735BECAAE706487CAFB323AAAFE3D15B1D60311ABA7432669949493DA0684E5[...]000409DA
| checksum: e692
| keyid: 16B218085F19B4DA
| # off=1371 ctb=b4 tag=13 hlen=2 plen=55
| :user ID packet: "Marcel Logen (RSA-Testkey) <33320000...@ybtra.de>"
| t20$

Hier die Rohdaten (Signatur abgeschnitten) als Hexdump:

| 00000000 95 05 58 04 61 40 7A 80 01 0C 00 C0 B4 12 2C 2C |..X.a@z.......,,|
| 00000016 ED B6 0A 44 82 2B 80 73 A0 DC 21 70 75 4A 32 86 |...D.+.s..!puJ2.|
| 00000032 9B 0C 50 61 0A F6 8F E4 8C D4 3F 0F 7B 24 97 CE |..Pa......?.{$..|
| 00000048 E8 FA CE 63 41 11 B3 16 B6 89 7D E5 A9 07 80 67 |...cA.....}....g|
| 00000064 F1 D4 D6 56 E2 F5 46 2D 81 D9 28 E7 8C 71 8E 0A |...V..F-..(..q..|
| 00000080 49 9D 6A F8 01 81 85 2B FD D9 C7 0A FC F1 92 1F |I.j....+........|
| 00000096 CD 21 C3 B2 42 48 DA 0A 33 13 30 2C D1 80 9D 50 |.!..BH..3.0,...P|
| 00000112 DF D2 2F 19 09 19 BF 2A 73 30 EF CE 90 68 33 0F |../....*s0...h3.|
| 00000128 16 49 FF 4D 6A 46 9B 8D F4 55 C8 37 6D 42 95 3A |.I.MjF...U.7mB.:|
| 00000144 27 A0 A1 B1 5B F3 81 C2 63 FA F3 65 52 C0 FD CD |'...[...c..eR...|
| 00000160 66 E8 49 94 11 3C 13 3F FC 62 A4 82 A3 51 5C 15 |f.I..<.?.b...Q\.|
| 00000176 44 F5 A5 61 C4 C9 90 83 B8 E1 9C D4 C0 8D 57 D7 |D..a..........W.|
| 00000192 05 E7 65 AD D0 10 05 BA 5C BF D7 3F 65 7D 83 C5 |..e.....\..?e}..|
| 00000208 DB F2 05 C8 7B B5 AE 59 63 2D D0 C2 CC 2F 00 34 |....{..Yc-.../.4|
| 00000224 55 A2 AF 7D 60 B0 BB A7 7B 12 95 BC 26 A8 37 04 |U..}`...{...&.7.|
| 00000240 63 82 2F 42 9A A4 68 D0 7C 52 6D 67 22 09 5B 4C |c./B..h.|Rmg".[L|
| 00000256 AF 75 25 32 72 A1 AB 2C FF 1C 48 83 BB BE 72 83 |.u%2r..,..H...r.|
| 00000272 A8 31 CD 07 AF FF 77 25 A1 EE 4C 7C 4F C7 DF 35 |.1....w%..L|O..5|
| 00000288 7E F3 9B 1A 39 A2 15 B3 FC 4A 42 B6 7F 17 46 60 |~...9....JB...F`|
| 00000304 31 B3 22 D3 D4 1B 29 C4 DA 39 95 02 4F 48 2D 3B |1."...)..9..OH-;|
| 00000320 0D 23 8A 2A 01 2F 10 99 C1 BB C8 D3 85 87 F9 3A |.#.*./.........:|
| 00000336 2A 48 8A 6F EA 92 82 86 6E E2 A1 8C E3 EA A2 AA |*H.o....n.......|
| 00000352 DB C6 7E 3E 1E A2 0E FA A9 6E C2 CD B2 3A AA 68 |..~>.....n...:.h|
| 00000368 6A 70 E2 B0 10 E0 C9 FF BF C4 CA 13 B4 C1 EF 26 |jp.............&|
| 00000384 DC 4B D7 3C 51 93 EB 76 0B 16 A9 00 11 01 00 01 |.K.<Q..v........|
| 00000400 00 0B FC 0A D9 D8 F0 1D DE 36 28 4B DA 9C 97 D0 |.........6(K....|
^^ = secret key ist unverschlüsselt
| 00000416 C0 57 C4 EB 9A 89 D6 B5 D7 AD E6 2A 20 BE 3E 34 |.W.........* .>4|
| 00000432 B0 C2 BE D8 F5 FB DB 2F 2E 7F F8 F6 83 D2 7A FD |......./......z.|
| 00000448 7B 6D 30 91 54 66 F4 BC 65 AA 06 21 17 09 ED 58 |{m0.Tf..e..!...X|
| 00000464 0B 53 6E C7 38 69 A8 85 91 C6 F3 20 0B 4D AA 1C |.Sn.8i..... .M..|
| 00000480 63 B5 F5 F6 FB 6E A0 3B 79 87 3E 32 CA 78 0F 0C |c....n.;y.>2.x..|
| 00000496 65 FB 32 F4 ED C8 75 3D F9 97 27 49 C7 46 68 DF |e.2...u=..'I.Fh.|
| 00000512 A6 0E DF B7 5C FA FB C2 62 0F 41 4E 05 A9 A6 2C |....\...b.AN...,|
| 00000528 0F 27 1E C2 BD 91 F3 3F 36 BE 07 D2 29 E0 58 B2 |.'.....?6...).X.|
| 00000544 83 D8 BC B3 3C 3E B1 21 4B 7B 27 06 D7 15 9A 96 |....<>.!K{'.....|
| 00000560 8E CA AB 2D 79 59 7A 7A EE CA CF 9E 3A C0 DD 8A |...-yYzz....:...|
| 00000576 07 F3 6F 01 02 90 08 48 8B AF 8F A7 D8 40 74 0C |..o....H.....@t.|
| 00000592 C8 C3 90 97 F0 38 2E EE EA CF 63 70 F9 D6 BB 43 |.....8....cp...C|
| 00000608 6B 3E 31 7F 06 29 4E DE E4 80 FD 58 3C 71 95 E8 |k>1..)N....X<q..|
| 00000624 DC 18 87 6F 00 CD 71 1E 2B D1 FE B3 1A 4F 46 53 |...o..q.+....OFS|
| 00000640 05 1A A4 9F 0C 7B AF AC 47 02 75 6A A1 D6 3B 58 |.....{..G.uj..;X|
| 00000656 07 FA 4B BF BE DD F0 BC 85 CA 16 B4 25 09 9F F9 |..K.........%...|
| 00000672 65 63 48 27 F9 28 06 6B 3A A4 5C 5C C0 F0 F6 2E |ecH'.(.k:.\\....|
| 00000688 B8 5B C0 E9 A0 AD 04 4C B2 33 B0 AE E2 73 A1 97 |.[.....L.3...s..|
| 00000704 50 7C DB 67 E4 B7 EA 40 D2 EB D1 4A 78 B2 B0 2B |P|.g...@...Jx..+|
| 00000720 05 F5 1C 84 88 A0 65 E2 BE 6B 5F D6 66 8F E7 E9 |......e..k_.f...|
| 00000736 E9 3D B7 9A D9 02 D5 E9 15 92 62 95 50 EA FC 1C |.=........b.P...|
| 00000752 C1 89 E5 2A 9A AE DB B9 05 68 DC 2D 2F E9 EB 80 |...*.....h.-/...|
| 00000768 2B AB F6 8A 66 A7 42 1B 7F BD C1 C6 96 33 9A 32 |+...f.B......3.2|
| 00000784 80 34 55 06 00 D4 CE 85 01 AF 0A BF E6 0A 82 B1 |.4U.............|
| 00000800 5E 4F 6D C1 7E 15 B6 CF 3B D5 A5 B6 8E 79 6F CE |^Om.~...;....yo.|
| 00000816 39 6D DF 6B 6C A6 14 27 7B BF 4C 8E F5 4A 6F 46 |9m.kl..'{.L..JoF|
| 00000832 55 58 D6 34 F4 2B ED A6 3A 50 AC 8A C3 B2 F5 46 |UX.4.+..:P.....F|
| 00000848 32 64 15 31 A2 AA 0A B5 2A D9 46 40 B5 B6 B3 C7 |2d.1....*.F@....|
| 00000864 88 92 90 E1 4A 35 50 6D B6 41 C1 75 8C CD 9C B1 |....J5Pm.A.u....|
| 00000880 90 EA BB CD 1D 49 AB EC 8F 05 F7 ED D4 13 A2 DE |.....I..........|
| 00000896 8F 54 FE BC FB 41 61 2E 46 59 A2 89 E2 FA F0 1C |.T...Aa.FY......|
| 00000912 D6 6B 31 CA 64 15 6B F3 90 79 15 31 0E 4B 86 C4 |.k1.d.k..y.1.K..|
| 00000928 77 77 44 C5 9C 6E 43 4E 44 D1 C0 50 61 D0 70 1D |wwD..nCND..Pa.p.|
| 00000944 D4 57 57 B8 62 09 B4 2F 34 E7 90 83 E6 EF 27 66 |.WW.b../4.....'f|
| 00000960 AD B4 65 D8 3A 0D D2 BE 80 1F 98 D7 FD A9 91 11 |..e.:...........|
| 00000976 08 89 2F 80 2B 06 00 E7 D0 FA A5 E6 81 C4 C1 71 |../.+..........q|
| 00000992 40 B2 61 0C 1E CB 78 95 61 EF 9D B1 89 27 08 F3 |@.a...x.a....'..|
| 00001008 89 B8 60 57 64 03 98 34 2F 8F B2 AB F2 79 0D 5B |..`Wd..4/....y.[|
| 00001024 81 D8 A1 FA E4 21 EE AC 74 C8 07 63 A6 53 08 00 |.....!..t..c.S..|
| 00001040 FC 97 94 8F 9D 55 02 FD 24 B2 D3 5E 5C C4 14 EB |.....U..$..^\...|
| 00001056 1F 03 1D F9 E5 0B CA B7 90 61 FB 67 83 E5 AB FE |.........a.g....|
| 00001072 51 AB 53 1D A9 4C 3E 8E 97 2F A4 AA 5C 26 D3 C9 |Q.S..L>../..\&..|
| 00001088 57 02 01 62 ED 06 8A 1D C9 0C 2B 22 D2 14 5A C9 |W..b......+"..Z.|
| 00001104 76 80 B8 74 C1 A6 29 BB A3 8A 03 AB F3 11 A3 D6 |v..t..).........|
| 00001120 6F 9F 70 83 BE 09 71 F2 1E 43 3B 25 32 40 6E 42 |o.p...q..C;%2@nB|
| 00001136 91 62 18 C1 C6 1D F7 EF 73 AA 38 41 F2 3C 9A 66 |.b......s.8A.<.f|
| 00001152 84 1E 8F 1E 86 A8 A2 5B 96 8F E1 11 2B BB B4 75 |.......[....+..u|
| 00001168 98 49 53 DA 66 86 7B 05 FF 4D 02 17 CB F1 62 91 |.IS.f.{..M....b.|
| 00001184 64 C7 35 BE CA AE 70 64 87 CA FB 32 3A AA FE 3D |d.5...pd...2:..=|
| 00001200 15 B1 D6 03 11 AB A7 43 26 69 94 94 93 DA 06 84 |.......C&i......|
| 00001216 E5 AC 20 C4 FE 0A 98 9F 2D E7 60 CF 7E 4F A5 EE |.. .....-.`.~O..|
| 00001232 15 D1 35 13 E7 44 4A 62 F3 3D EA AF 80 78 2E 15 |..5..DJb.=...x..|
| 00001248 43 97 8B 56 CE 0F FC C6 F8 DE 40 C0 9C 51 BE 71 |C..V......@..Q.q|
| 00001264 8F 84 A8 A2 4B 63 93 2C A9 20 16 44 EA 37 C8 8B |....Kc.,. .D.7..|
| 00001280 EF A7 4C 15 0B 50 3B C8 3D 19 1B 20 40 41 8A 4B |..L..P;.=.. @A.K|
| 00001296 7E C6 99 4C 74 CA 8C D7 02 5B DC C0 08 81 C0 0B |~..Lt....[......|
| 00001312 82 6C 19 45 8C EC F2 E2 14 D9 74 23 6E 48 B5 D1 |.l.E......t#nH..|
| 00001328 7A 68 18 35 48 E8 F7 26 BB E4 48 71 AC 6A 97 8B |zh.5H..&..Hq.j..|
| 00001344 08 D7 63 F9 6C 09 8A 8D A8 DF 2F 72 21 05 23 8A |..c.l...../r!.#.|
| 00001360 EB 5D 13 1D 8C 00 04 09 DA E6 92 B4 37 4D 61 72 |.]..........7Mar|
^^^^^ checksum
| 00001376 63 65 6C 20 4C 6F 67 65 6E 20 28 52 53 41 2D 54 |cel Logen (RSA-T|
| 00001392 65 73 74 6B 65 79 29 20 3C 33 33 33 32 30 30 30 |estkey) <3332000|
| 00001408 30 37 31 31 30 2D 30 32 30 31 40 79 62 74 72 61 |07110-0201@ybtra|
| 00001424 2E 64 65 3E 89 01 D4 04 13 01 08 00 3E 16 21 04 |.de>........>.!.|
[...]

Frage natürlich: Wie berechnet sich die checksum?

Der aktuelle OpenPGP-Draft sagt dazu:

<https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-crypto-refresh-05#section-5.5.3>

| * If the string-to-key usage octet is zero, then a two-octet
| checksum of the algorithm-specific portion (sum of all octets, mod
| 65536).

Meine Erkenntnis: Hier dürfen nur die secret Daten berücksichtigt
werden, obwohl weiter oben im Draft steht:

| 5.5.3. Secret-Key Packet Formats
|
| The Secret-Key and Secret-Subkey packets contain all the data of the
| Public-Key and Public-Subkey packets, with additional algorithm-
| specific secret-key data appended, usually in encrypted form.
|
| The packet contains:
|
| * The fields of a Public-Key or Public-Subkey packet, as described
| above.
|
| * One octet indicating string-to-key usage conventions. Zero
| indicates that the secret-key data is not encrypted. 255, 254, or
[...]

Demnach sollten die public Anteile auch in der checksum Berück-
sichtigung finden, oder nicht?

Wie dem auch sei: Es werden (von GnuPG) nur die Oktetts des secret
Anteils summiert (wobei auch die Längenangaben der MPI - multipre-
cision integers - mit erfaßt werden müssen).

| t20$ head -n 20 rsa-testkeygpg-fuer-checksum-e692.3
| 0B
| FC
| 0A
| D9
| D8
| F0
| 1D
| DE
| 36
| 28
| 4B
| DA
| 9C
| 97
| D0
| C0
| 57
| C4
| EB
| 9A
| t20$ tail -n 20 rsa-testkeygpg-fuer-checksum-e692.3
| 09
| 8A
| 8D
| A8
| DF
| 2F
| 72
| 21
| 05
| 23
| 8A
| EB
| 5D
| 13
| 1D
| 8C
| 00
| 04
| 09
| DA
| t20$

Berechnung der Oktett-Summe (mit ksh und bc):

| t20$ sumq=0; while read ; do sumq=$(echo 'obase=16;ibase=16;' "$sumq" "+" "$REPLY" |bc) && echo "$REPLY" " " "$sumq" ;done < rsa-testkeygpg-fuer-checksum-e692.3 && echo "$sumq"
| 0B B
| FC 107
| 0A 111
| D9 1EA
| D8 2C2
| F0 3B2
| 1D 3CF
| DE 4AD
| 36 4E3
| 28 50B
| 4B 556
| DA 630
| 9C 6CC
| 97 763
| D0 833
| C0 8F3
| 57 94A
| C4 A0E
| EB AF9
| 9A B93
| 89 C1C
| D6 CF2
| B5 DA7
| D7 E7E
| AD F2B
| E6 1011
| 2A 103B
[...]
| 5D 1E4EF
| 13 1E502
| 1D 1E51F
| 8C 1E5AB
| 00 1E5AB
| 04 1E5AF
| 09 1E5B8
| DA 1E692
| 1E692
| t20$

0x1E692 mod 0x10000 = E692

Das entspricht der von GnuPG angezeigten checksum!

Bezieht man die public Anteile mit ein, kommt eine Summe von 0x2A5C8
(bzw. mod 65536 0xA5CB) heraus.

Marcel 1ee0v (1521695)
--
╭──╮ ╭──╮ ╭─╮ ╭──╮ ╭───╮ ╭───╮ ╭──
───╮ │ ╰─╯ ╰─╯ ╰──╯ ╰───╯ ╰──╮ ╭────╯ │ ╭───╮ │
│ ╰──╮ ╭────────╯ ╭─╯ ╭──╯ │ │ ╭───╯
╰─────╯ ╰──────────╯ ╰───────────╯ ╰───╯ef4ab7

Marcel Logen

unread,
Apr 27, 2022, 7:28:19 PM4/27/22
to
Marcel Logen in de.test:

>Als ich kürzlich noch mal meinen unverschlüsselten RSA3072-Test-
>und Analyse-Key ausgegraben habe, stellte ich fest, daß dort im
>secret key eine checksum angegeben ist.

[...]

>| t20$ gpg --list-packets rsa-testkeygpg.gpg
>| # off=0 ctb=95 tag=5 hlen=3 plen=1368
>| :secret key packet:
>| version 4, algo 1, created 1631615616, expires 0
>| pkey[0]: [3072 bits]
>| pkey[1]: [17 bits]
>| skey[2]: [3068 bits]
>| skey[3]: [1536 bits]
>| skey[4]: [1536 bits]
>| skey[5]: [1535 bits]
[...]

>| t20$ gpg --verbose --list-packets rsa-testkeygpg.gpg | head -n 13 | sed -e 's/^\(.\{90\}\).*\(.\{8\}\)$/\1[...]\2/'
>| # off=0 ctb=95 tag=5 hlen=3 plen=1368
>| :secret key packet:
>| version 4, algo 1, created 1631615616, expires 0
>| pkey[0]: C0B4122C2CEDB60A44822B8073A0DC2170754A32869B0C50610AF68FE48CD43F0F7B2497CEE8FACE[...]760B16A9
>| pkey[1]: 010001
>| skey[2]: 0AD9D8F01DDE36284BDA9C97D0C057C4EB9A89D6B5D7ADE62A20BE3E34B0C2BED8F5FBDB2F2E7FF8[...]32803455
>| skey[3]: D4CE8501AF0ABFE60A82B15E4F6DC17E15B6CF3BD5A5B68E796FCE396DDF6B6CA614277BBF4C8EF5[...]892F802B
>| skey[4]: E7D0FAA5E681C4C17140B2610C1ECB789561EF9DB1892708F389B86057640398342F8FB2ABF2790D[...]DA66867B
>| skey[5]: 4D0217CBF1629164C735BECAAE706487CAFB323AAAFE3D15B1D60311ABA7432669949493DA0684E5[...]000409DA
[...]

<https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-crypto-refresh-05#section-5.6>,
dort Nr. 5.6.1 (RSA):

| 5.6.1. Algorithm-Specific Part for RSA Keys
|
| The public key is this series of multiprecision integers:
|
| * MPI of RSA public modulus n;
|
| * MPI of RSA public encryption exponent e.
|
| The secret key is this series of multiprecision integers:
|
| * MPI of RSA secret exponent d;
|
| * MPI of RSA secret prime value p;
|
| * MPI of RSA secret prime value q (p < q);
|
| * MPI of u, the multiplicative inverse of p, mod q.

>Hier die Rohdaten (Signatur abgeschnitten) als Hexdump:
>
>| 00000000 95 05 58 04 61 40 7A 80 01 0C 00 C0 B4 12 2C 2C |..X.a@z.......,,|
^^ ^^ ^^ ^^ = Zeitpunkt der Schlüssel-Erstellung
^^ 01 = RSA
^^ ^^ = MPI-Länge (3072)
^^ ^^ ^^ = Start public key (Modulus)
>| 00000016 ED B6 0A 44 82 2B 80 73 A0 DC 21 70 75 4A 32 86 |...D.+.s..!puJ2.|
>| 00000032 9B 0C 50 61 0A F6 8F E4 8C D4 3F 0F 7B 24 97 CE |..Pa......?.{$..|
>| 00000048 E8 FA CE 63 41 11 B3 16 B6 89 7D E5 A9 07 80 67 |...cA.....}....g|
>| 00000064 F1 D4 D6 56 E2 F5 46 2D 81 D9 28 E7 8C 71 8E 0A |...V..F-..(..q..|
>| 00000080 49 9D 6A F8 01 81 85 2B FD D9 C7 0A FC F1 92 1F |I.j....+........|
>| 00000096 CD 21 C3 B2 42 48 DA 0A 33 13 30 2C D1 80 9D 50 |.!..BH..3.0,...P|
>| 00000112 DF D2 2F 19 09 19 BF 2A 73 30 EF CE 90 68 33 0F |../....*s0...h3.|
>| 00000128 16 49 FF 4D 6A 46 9B 8D F4 55 C8 37 6D 42 95 3A |.I.MjF...U.7mB.:|
>| 00000144 27 A0 A1 B1 5B F3 81 C2 63 FA F3 65 52 C0 FD CD |'...[...c..eR...|
>| 00000160 66 E8 49 94 11 3C 13 3F FC 62 A4 82 A3 51 5C 15 |f.I..<.?.b...Q\.|
>| 00000176 44 F5 A5 61 C4 C9 90 83 B8 E1 9C D4 C0 8D 57 D7 |D..a..........W.|
>| 00000192 05 E7 65 AD D0 10 05 BA 5C BF D7 3F 65 7D 83 C5 |..e.....\..?e}..|
>| 00000208 DB F2 05 C8 7B B5 AE 59 63 2D D0 C2 CC 2F 00 34 |....{..Yc-.../.4|
>| 00000224 55 A2 AF 7D 60 B0 BB A7 7B 12 95 BC 26 A8 37 04 |U..}`...{...&.7.|
>| 00000240 63 82 2F 42 9A A4 68 D0 7C 52 6D 67 22 09 5B 4C |c./B..h.|Rmg".[L|
>| 00000256 AF 75 25 32 72 A1 AB 2C FF 1C 48 83 BB BE 72 83 |.u%2r..,..H...r.|
>| 00000272 A8 31 CD 07 AF FF 77 25 A1 EE 4C 7C 4F C7 DF 35 |.1....w%..L|O..5|
>| 00000288 7E F3 9B 1A 39 A2 15 B3 FC 4A 42 B6 7F 17 46 60 |~...9....JB...F`|
>| 00000304 31 B3 22 D3 D4 1B 29 C4 DA 39 95 02 4F 48 2D 3B |1."...)..9..OH-;|
>| 00000320 0D 23 8A 2A 01 2F 10 99 C1 BB C8 D3 85 87 F9 3A |.#.*./.........:|
>| 00000336 2A 48 8A 6F EA 92 82 86 6E E2 A1 8C E3 EA A2 AA |*H.o....n.......|
>| 00000352 DB C6 7E 3E 1E A2 0E FA A9 6E C2 CD B2 3A AA 68 |..~>.....n...:.h|
>| 00000368 6A 70 E2 B0 10 E0 C9 FF BF C4 CA 13 B4 C1 EF 26 |jp.............&|
>| 00000384 DC 4B D7 3C 51 93 EB 76 0B 16 A9 00 11 01 00 01 |.K.<Q..v........|
^^ ^^ ^^ = Ende public key (Modulus)
^^ ^^ = MPI-Länge (17 Bit)
^^ ^^ ^^ = public Exponent e (65537)
>| 00000400 00 0B FC 0A D9 D8 F0 1D DE 36 28 4B DA 9C 97 D0 |.........6(K....|
> ^^ = secret key ist unverschlüsselt
^^ ^^ = MPI-Längenindikator (0x0BFC = 3068)
^^ ^^ ^^ ... = Exponent d
>| 00000416 C0 57 C4 EB 9A 89 D6 B5 D7 AD E6 2A 20 BE 3E 34 |.W.........* .>4|
>| 00000432 B0 C2 BE D8 F5 FB DB 2F 2E 7F F8 F6 83 D2 7A FD |......./......z.|
>| 00000448 7B 6D 30 91 54 66 F4 BC 65 AA 06 21 17 09 ED 58 |{m0.Tf..e..!...X|
>| 00000464 0B 53 6E C7 38 69 A8 85 91 C6 F3 20 0B 4D AA 1C |.Sn.8i..... .M..|
>| 00000480 63 B5 F5 F6 FB 6E A0 3B 79 87 3E 32 CA 78 0F 0C |c....n.;y.>2.x..|
>| 00000496 65 FB 32 F4 ED C8 75 3D F9 97 27 49 C7 46 68 DF |e.2...u=..'I.Fh.|
>| 00000512 A6 0E DF B7 5C FA FB C2 62 0F 41 4E 05 A9 A6 2C |....\...b.AN...,|
>| 00000528 0F 27 1E C2 BD 91 F3 3F 36 BE 07 D2 29 E0 58 B2 |.'.....?6...).X.|
>| 00000544 83 D8 BC B3 3C 3E B1 21 4B 7B 27 06 D7 15 9A 96 |....<>.!K{'.....|
>| 00000560 8E CA AB 2D 79 59 7A 7A EE CA CF 9E 3A C0 DD 8A |...-yYzz....:...|
>| 00000576 07 F3 6F 01 02 90 08 48 8B AF 8F A7 D8 40 74 0C |..o....H.....@t.|
>| 00000592 C8 C3 90 97 F0 38 2E EE EA CF 63 70 F9 D6 BB 43 |.....8....cp...C|
>| 00000608 6B 3E 31 7F 06 29 4E DE E4 80 FD 58 3C 71 95 E8 |k>1..)N....X<q..|
>| 00000624 DC 18 87 6F 00 CD 71 1E 2B D1 FE B3 1A 4F 46 53 |...o..q.+....OFS|
>| 00000640 05 1A A4 9F 0C 7B AF AC 47 02 75 6A A1 D6 3B 58 |.....{..G.uj..;X|
>| 00000656 07 FA 4B BF BE DD F0 BC 85 CA 16 B4 25 09 9F F9 |..K.........%...|
>| 00000672 65 63 48 27 F9 28 06 6B 3A A4 5C 5C C0 F0 F6 2E |ecH'.(.k:.\\....|
>| 00000688 B8 5B C0 E9 A0 AD 04 4C B2 33 B0 AE E2 73 A1 97 |.[.....L.3...s..|
>| 00000704 50 7C DB 67 E4 B7 EA 40 D2 EB D1 4A 78 B2 B0 2B |P|.g...@...Jx..+|
>| 00000720 05 F5 1C 84 88 A0 65 E2 BE 6B 5F D6 66 8F E7 E9 |......e..k_.f...|
>| 00000736 E9 3D B7 9A D9 02 D5 E9 15 92 62 95 50 EA FC 1C |.=........b.P...|
>| 00000752 C1 89 E5 2A 9A AE DB B9 05 68 DC 2D 2F E9 EB 80 |...*.....h.-/...|
>| 00000768 2B AB F6 8A 66 A7 42 1B 7F BD C1 C6 96 33 9A 32 |+...f.B......3.2|
>| 00000784 80 34 55 06 00 D4 CE 85 01 AF 0A BF E6 0A 82 B1 |.4U.............|
^^ ^^ ^^ = Ende Exponent d
^^ ^^ MPI-Länge (0x0600 = 1536)
^^ ^^ ^^ ... = Primzahl p
>| 00000800 5E 4F 6D C1 7E 15 B6 CF 3B D5 A5 B6 8E 79 6F CE |^Om.~...;....yo.|
>| 00000816 39 6D DF 6B 6C A6 14 27 7B BF 4C 8E F5 4A 6F 46 |9m.kl..'{.L..JoF|
>| 00000832 55 58 D6 34 F4 2B ED A6 3A 50 AC 8A C3 B2 F5 46 |UX.4.+..:P.....F|
>| 00000848 32 64 15 31 A2 AA 0A B5 2A D9 46 40 B5 B6 B3 C7 |2d.1....*.F@....|
>| 00000864 88 92 90 E1 4A 35 50 6D B6 41 C1 75 8C CD 9C B1 |....J5Pm.A.u....|
>| 00000880 90 EA BB CD 1D 49 AB EC 8F 05 F7 ED D4 13 A2 DE |.....I..........|
>| 00000896 8F 54 FE BC FB 41 61 2E 46 59 A2 89 E2 FA F0 1C |.T...Aa.FY......|
>| 00000912 D6 6B 31 CA 64 15 6B F3 90 79 15 31 0E 4B 86 C4 |.k1.d.k..y.1.K..|
>| 00000928 77 77 44 C5 9C 6E 43 4E 44 D1 C0 50 61 D0 70 1D |wwD..nCND..Pa.p.|
>| 00000944 D4 57 57 B8 62 09 B4 2F 34 E7 90 83 E6 EF 27 66 |.WW.b../4.....'f|
>| 00000960 AD B4 65 D8 3A 0D D2 BE 80 1F 98 D7 FD A9 91 11 |..e.:...........|
>| 00000976 08 89 2F 80 2B 06 00 E7 D0 FA A5 E6 81 C4 C1 71 |../.+..........q|
^^ ^^ ^^ = Ende Primzahl p
^^ ^^ = MPI-Länge (1536)
^^ ^^ ^^ ... = Primzahl q
>| 00000992 40 B2 61 0C 1E CB 78 95 61 EF 9D B1 89 27 08 F3 |@.a...x.a....'..|
>| 00001008 89 B8 60 57 64 03 98 34 2F 8F B2 AB F2 79 0D 5B |..`Wd..4/....y.[|
>| 00001024 81 D8 A1 FA E4 21 EE AC 74 C8 07 63 A6 53 08 00 |.....!..t..c.S..|
>| 00001040 FC 97 94 8F 9D 55 02 FD 24 B2 D3 5E 5C C4 14 EB |.....U..$..^\...|
>| 00001056 1F 03 1D F9 E5 0B CA B7 90 61 FB 67 83 E5 AB FE |.........a.g....|
>| 00001072 51 AB 53 1D A9 4C 3E 8E 97 2F A4 AA 5C 26 D3 C9 |Q.S..L>../..\&..|
>| 00001088 57 02 01 62 ED 06 8A 1D C9 0C 2B 22 D2 14 5A C9 |W..b......+"..Z.|
>| 00001104 76 80 B8 74 C1 A6 29 BB A3 8A 03 AB F3 11 A3 D6 |v..t..).........|
>| 00001120 6F 9F 70 83 BE 09 71 F2 1E 43 3B 25 32 40 6E 42 |o.p...q..C;%2@nB|
>| 00001136 91 62 18 C1 C6 1D F7 EF 73 AA 38 41 F2 3C 9A 66 |.b......s.8A.<.f|
>| 00001152 84 1E 8F 1E 86 A8 A2 5B 96 8F E1 11 2B BB B4 75 |.......[....+..u|
>| 00001168 98 49 53 DA 66 86 7B 05 FF 4D 02 17 CB F1 62 91 |.IS.f.{..M....b.|
^^ ^^ ^^ = Ende Primzahl q
^^ ^^ = MPI-Länge (1535)
^^ ^^ ... = Start u
>| 00001184 64 C7 35 BE CA AE 70 64 87 CA FB 32 3A AA FE 3D |d.5...pd...2:..=|
>| 00001200 15 B1 D6 03 11 AB A7 43 26 69 94 94 93 DA 06 84 |.......C&i......|
>| 00001216 E5 AC 20 C4 FE 0A 98 9F 2D E7 60 CF 7E 4F A5 EE |.. .....-.`.~O..|
>| 00001232 15 D1 35 13 E7 44 4A 62 F3 3D EA AF 80 78 2E 15 |..5..DJb.=...x..|
>| 00001248 43 97 8B 56 CE 0F FC C6 F8 DE 40 C0 9C 51 BE 71 |C..V......@..Q.q|
>| 00001264 8F 84 A8 A2 4B 63 93 2C A9 20 16 44 EA 37 C8 8B |....Kc.,. .D.7..|
>| 00001280 EF A7 4C 15 0B 50 3B C8 3D 19 1B 20 40 41 8A 4B |..L..P;.=.. @A.K|
>| 00001296 7E C6 99 4C 74 CA 8C D7 02 5B DC C0 08 81 C0 0B |~..Lt....[......|
>| 00001312 82 6C 19 45 8C EC F2 E2 14 D9 74 23 6E 48 B5 D1 |.l.E......t#nH..|
>| 00001328 7A 68 18 35 48 E8 F7 26 BB E4 48 71 AC 6A 97 8B |zh.5H..&..Hq.j..|
>| 00001344 08 D7 63 F9 6C 09 8A 8D A8 DF 2F 72 21 05 23 8A |..c.l...../r!.#.|
>| 00001360 EB 5D 13 1D 8C 00 04 09 DA E6 92 B4 37 4D 61 72 |.]..........7Mar|
^^ ^^ ^^ = Ende u

(p * u) mod q = 1

u ist das multiplikative Inverse zu p, mod q.

Mal prüfen, ob das auch stimmt ... ;-)

(Ich habe hier statt "u" "inv" genommen.)

| t20$ cat p
| D4CE8501AF0ABFE60A82B15E4F6DC17E15B6CF3BD5A5B68E796FCE396DDF6B6CA614277BBF4C8EF54A6F465558D634F42BEDA63A50AC8AC3B2F54632641531A2AA0AB52AD94640B5B6B3C7889290E14A35506DB641C1758CCD9CB190EABBCD1D49ABEC8F05F7EDD413A2DE8F54FEBCFB41612E4659A289E2FAF01CD66B31CA64156BF3907915310E4B86C4777744C59C6E434E44D1C05061D0701DD45757B86209B42F34E79083E6EF2766ADB465D83A0DD2BE801F98D7FDA9911108892F802B

| t20$ cat q
| E7D0FAA5E681C4C17140B2610C1ECB789561EF9DB1892708F389B86057640398342F8FB2ABF2790D5B81D8A1FAE421EEAC74C80763A6530800FC97948F9D5502FD24B2D35E5CC414EB1F031DF9E50BCAB79061FB6783E5ABFE51AB531DA94C3E8E972FA4AA5C26D3C957020162ED068A1DC90C2B22D2145AC97680B874C1A629BBA38A03ABF311A3D66F9F7083BE0971F21E433B2532406E42916218C1C61DF7EF73AA3841F23C9A66841E8F1E86A8A25B968FE1112BBBB475984953DA66867B

| t20$ cat inv
| 4D0217CBF1629164C735BECAAE706487CAFB323AAAFE3D15B1D60311ABA7432669949493DA0684E5AC20C4FE0A989F2DE760CF7E4FA5EE15D13513E7444A62F33DEAAF80782E1543978B56CE0FFCC6F8DE40C09C51BE718F84A8A24B63932CA9201644EA37C88BEFA74C150B503BC83D191B2040418A4B7EC6994C74CA8CD7025BDCC00881C00B826C19458CECF2E214D974236E48B5D17A68183548E8F726BBE44871AC6A978B08D763F96C098A8DA8DF2F722105238AEB5D131D8C000409DA

| t20$ openssl prime $( (echo 'ibase=16;' && cat p )|bc | tr -d '\\\012')
| 2003635447515229209836454789888721872919494576702920527546430406328255442141581135165217445153831270830540245117326263210091823933664810006891543730430125939705182206360834403500704162680568742966335469947935496866287276586597060043656237170231871443378116140418206449225132080643709473071988028053118943235455302601618371237472044180652041092121933509423731863659309307936798007019886907330287917322834402638275769310619660620045811197125616369819327974524026923 is prime

| t20$ openssl prime $( (echo 'ibase=16;' && cat q )|bc | tr -d '\\\012')
| 2182616280906543031852662079890736369501294412782549604116551327563192454342379915638742806827552540592452644361508143782662688514417922674131149642361741802411019397020525111609371878486156580038103512641694866187812933579677704114463350705853841599372190975324474795079353296907472805387575519849082672796369718382327063975662796219585599764452127107299469952198457282216384444454257815885858218579563830566304783280687815161016277355731832669652931907064071803 is prime

Wie man sieht, ist p < q, und beide sind - vermutlich - Primzahlen.

| t20$ (echo -n 'scale=0;ibase=16;' && (cat p | tr -d '\012') && echo -n '*' && (cat inv | tr -d '\012') && echo -n '%' && cat q)|bc
| 1
| t20$

Es kommt tatsächlich "1" heraus, d. h. inv ist das multiplikative
Inverse von p, mod q.

Marcel 1hj91 (1625377)
--
╭─────╮ ╭──╮ ╭─────────╮ ╭──╮
╰─╮ ╰───╮ │ ╰─╮ ╭──────╯ │ ╭─╯ ╰───╮
╮ ╰──╮ ╰──╯ ╭─╯ ╰─╮ ╭───╯ ╰──╮ │ ╭──╮ ╭──╮ ╭───
╰─────╯ ╰──────╯ 6967cc ╰─────────╯ ╰────╯ ╰───╯ ╰─╯

Marcel Logen

unread,
Apr 27, 2022, 7:48:10 PM4/27/22
to
Marcel Logen in de.test:

[...]

><https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-crypto-refresh-05#section-5.6>,
>dort Nr. 5.6.1 (RSA):
>
>| 5.6.1. Algorithm-Specific Part for RSA Keys
>|
>| The public key is this series of multiprecision integers:
>|
>| * MPI of RSA public modulus n;
>|
>| * MPI of RSA public encryption exponent e.
>|
>| The secret key is this series of multiprecision integers:
>|
>| * MPI of RSA secret exponent d;
>|
>| * MPI of RSA secret prime value p;
>|
>| * MPI of RSA secret prime value q (p < q);
>|
>| * MPI of u, the multiplicative inverse of p, mod q.

[...]

>>| 00000000 95 05 58 04 61 40 7A 80 01 0C 00 C0 B4 12 2C 2C |..X.a@z.......,,|
> ^^ ^^ ^^ ^^ = Zeitpunkt der Schlüssel-Erstellung

| t20$ bc -l
| ibase=16
| 61407A80
| 1631615616

| t20$ date -j -r 1631615616
| Tue Sep 14 12:33:36 CEST 2021
| t20$

(mit BSD-date)

Das stimmt:

| t20$ gpg --show-key rsa-testkeygpg.gpg | head -n 1
| sec rsa3072 2021-09-14 [SC] [expired: 2021-09-30]
| t20$

[...]

>(p * u) mod q = 1
>
>u ist das multiplikative Inverse zu p, mod q.
>
>Mal prüfen, ob das auch stimmt ... ;-)

[...]

>Es kommt tatsächlich "1" heraus, d. h. inv ist das multiplikative
>Inverse von p, mod q.

Jetzt könnte man noch die Berechnungen aus den Punkten 1 bis 5 aus
<https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
durchführen.

Dies geschieht evtl. zu einem späteren Zeitpunkt. :-)

Marcel 1gp9s (1598780)
--
╭─╮ ╭─────────╮ ╭─────╮ ╭──╮ ╭──╮ ╭─╮ ╭────╮
╭───╯ ╰─╯ │ ╭────╮ ╭─╮ ╰─╮ ╰─╯ │ │ ╰───────╯ │ │ │
╰────╮ ╭─────────╯ ╭─╯ ╰─╯ ╰────╯ ╭─────╯ ╰─╮ ╭──╯ │ ╭─╯
╭─────╯ ╰───────────╯ ╰──────────╯ 3f957f╰─────╯ ╰───

Marcel Logen

unread,
Apr 27, 2022, 8:17:02 PM4/27/22
to
Marcel Logen in de.test:

>Jetzt könnte man noch die Berechnungen aus den Punkten 1 bis 5 aus
><https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
>durchführen.

Hier schon mal Punkt 1:

| t20$ ( echo -n 'obase=10;ibase=16;' && echo -n 'l(' && (cat p | tr -d '\012') && echo -n ')/l(2)' && echo -n '-' && echo -n 'l(' && ( cat q | tr -d '\012' ) && echo ')/l(2)' ) | bc -l
| -.12343847630185207129
| t20$

Der Betrag davon ist > 0,1 und < 30.

Und Punkt 2:

| t20$ ( echo -n 'obase=16;ibase=16;' && (cat p | tr -d '\012') && echo -n '*' && cat q ) | bc | tr -d '\\\012' > Npq

Die Datei "Npq" enthält also das Produkt von p und q (in Hex).
"N" enthält die Modulus-Daten aus dem Schlüsselmaterial.

| t20$ cmp N Npq
| cmp: EOF on Npq

Hier muß bei "Npq" am Ende noch ein newline hinzugefügt werden
(z. B. mit vim); danach sind die Dateien gleich:

| t20$ cmp N Npq
| t20$

Marcel 1gpve (1599470)
--
╭──╮ ╭─╮ ╭──────────╮ ╭──╮ ╭─────╮ ╭──╮
│ ╰─╮ ╭──────╮ │ │ │ ╭───────╯ │ ╰─╯ ╰─╯ ╰─╮ ╭─╮ ╭
─╮ ╭─╯ ╰─╮ │ ╭───╯ │ │ │ │ ╭────╮ ╰─╮ │ ╭──╯ ╰─╯
╰─╯ ╰─╯ ╰───────╯ ╰───╯ ╰─╯ ╰────╯ ╰─╯ afd134

Marcel Logen

unread,
Apr 28, 2022, 6:35:02 PM4/28/22
to
Marcel Logen in de.test:

>Jetzt könnte man noch die Berechnungen aus den Punkten 1 bis 5 aus
><https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
>durchführen.

Punkt 3:

| t20$ cat p
| D4CE8501AF0ABFE60A82B15E4F6DC17E15B6CF3BD5A5B68E796FCE396DDF6B6CA614277BBF4C8EF54A6F465558D634F42BEDA63A50AC8AC3B2F54632641531A2AA0AB52AD94640B5B6B3C7889290E14A35506DB641C1758CCD9CB190EABBCD1D49ABEC8F05F7EDD413A2DE8F54FEBCFB41612E4659A289E2FAF01CD66B31CA64156BF3907915310E4B86C4777744C59C6E434E44D1C05061D0701DD45757B86209B42F34E79083E6EF2766ADB465D83A0DD2BE801F98D7FDA9911108892F802B

| t20$ cat q
| E7D0FAA5E681C4C17140B2610C1ECB789561EF9DB1892708F389B86057640398342F8FB2ABF2790D5B81D8A1FAE421EEAC74C80763A6530800FC97948F9D5502FD24B2D35E5CC414EB1F031DF9E50BCAB79061FB6783E5ABFE51AB531DA94C3E8E972FA4AA5C26D3C957020162ED068A1DC90C2B22D2145AC97680B874C1A629BBA38A03ABF311A3D66F9F7083BE0971F21E433B2532406E42916218C1C61DF7EF73AA3841F23C9A66841E8F1E86A8A25B968FE1112BBBB475984953DA66867B

| t20$ ( ( echo -n 'obase=16;ibase=16;(' && (cat p | tr -d '\012') && echo -n '-1)*(' && (cat q | tr -d '\012') && echo '-1)' ) | bc | tr -d '\\\012' && echo ) > phiN

| t20$ cat phiN
| C0B4122C2CEDB60A44822B8073A0DC2170754A32869B0C50610AF68FE48CD43F0F7B2497CEE8FACE634111B316B6897DE5A9078067F1D4D656E2F5462D81D928E78C718E0A499D6AF80181852BFDD9C70AFCF1921FCD21C3B24248DA0A3313302CD1809D50DFD22F190919BF2A7330EFCE9068330F1649FF4D6A469B8DF455C8376D42953A27A0A1B15BF381C263FAF36552C0FDCD66E84994113C133FFC62A482A3515C1544F5A561C4C99083B8E19CD4C08D57D705E765ADD01005BA5CBFD582C5FDDC304F6D5E4CB851EEFDD6A0DA17B37026AD26C51810672A21E237A390E1E2F10899247A2C9CA985717CC1FB8A8EBF9B19985C97597E80C3E4394C95A2DC8C56744C052D0265DD34D0992C01378F6EF82D8C3998624E4B4531AB9730E6DE3BFB12AFDD9E7AF6DA3A990CEE760FA3250DBBBE98854C659A9181B9CE4B3B02760A65152205D84DF42E9A8B6C13932C825922B3E935AE2B1D2221E18B9868D48A613D3EE7B0615A655B8D2CD343EDAA4B738DF617B8251D28398F12751004
| t20$

Marcel 1i9e7 (1648071)
--
╭─╮ ╭─╮ ╭─╮ ╭──────╮ ╭─╮ ╭──╮ ╭───────╮
────╯ ╰─╯ │ │ ╰─╯ ╰─╮ ╭───╯ │ │ │ ╰───╮ ╰────
╭───────╯ │ ╭──────╯ ╭──╮ ╰─╮ ╰─╯ ╰─╮ ╭──╮ ╭─╮ ╭──╮ │
╰──────────╯ ╰────────╯ ╰────╯ ╰─╯ ╰─╯ ╰─╯ ╰─╯ e65b36

Marcel Logen

unread,
Apr 28, 2022, 7:30:03 PM4/28/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:

>>Jetzt könnte man noch die Berechnungen aus den Punkten 1 bis 5 aus
>><https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
>>durchführen.
>
>Punkt 3:

[...]

phiN = (p-1) * (q-1)

>| t20$ ( ( echo -n 'obase=16;ibase=16;(' && (cat p | tr -d '\012') && echo -n '-1)*(' && (cat q | tr -d '\012') && echo '-1)' ) | bc | tr -d '\\\012' && echo ) > phiN

Punkt 4:

e = 65537 = 0x10001

| t20$ factor 65537
| 65537: 65537
| t20$

e ist also eine Primzahl. Und 1 < e < phiN.

phiN / e ist nicht ganzzahlig, d. h. e und phiN sind teilerfremd:

| t20$ ( echo -n 'obase=16;ibase=16;' && (cat phiN | tr -d '\012') && echo '/10001' ) | bc -l
| C0B35178DB74DA9569ECC193B20D2A14466103D182C98986D7841F0BC5810EBE00BD\
| 23DAAB0E4FC01380FE32188470F974AF92D0D520FFB5572D9E188F6949BF9DCCD3C1\
| 368866E2911EF0663B979E2F6CCD84C49B0886BB2B871D52ECE0265006817A1BD6C3\
| FB6B1D9DFC212E52029DCBF29C4072D5D7297640D05ABD99982E9F3EA35696D109D0\
| A78B4BF6766D8485E0CCE030ED35FB1398FDA3159CE6C5BDBCE5947680CE74D6ECED\
| DCA2A7163A869A39F31DE3E8037DAA5265B354A96B2C1799E6424A0D235129672887\
| D54ECB8B4C2823FE89283BEFD47755AA8C8D1703CADF262972FB07319577EFF98CC8\
| 6EC21FFD7B1C1D407A190467BF7C79D01BD2C0B995BAB64A76B7EF2545AB5380ADB6\
| E1B8167575C4229E2BAD198492129ED43F67BBAAF432AA484C91EE071EE757284BFC\
| C1BEFCD98872DD27B45A057445C6BCAF4DB5C76C3E6C0F881F126C59A7398548D3D9\
| E00F559ED57E4CA394E80380D1099033AEB401AD58B802D529FE19EF905BE33212E5\
| A53F77E8C1A650CE.BF3540CABF3540CAA
| t20$

Punkt 5:

(e * d) mod phiN = 1

Klappt aber nicht:

| t20$ cat d
| 0AD9D8F01DDE36284BDA9C97D0C057C4EB9A89D6B5D7ADE62A20BE3E34B0C2BED8F5FBDB2F2E7FF8F683D27AFD7B6D30915466F4BC65AA06211709ED580B536EC73869A88591C6F3200B4DAA1C63B5F5F6FB6EA03B79873E32CA780F0C65FB32F4EDC8753DF9972749C74668DFA60EDFB75CFAFBC2620F414E05A9A62C0F271EC2BD91F33F36BE07D229E058B283D8BCB33C3EB1214B7B2706D7159A968ECAAB2D79597A7AEECACF9E3AC0DD8A07F36F01029008488BAF8FA7D840740CC8C39097F0382EEEEACF6370F9D6BB436B3E317F06294EDEE480FD583C7195E8DC18876F00CD711E2BD1FEB31A4F4653051AA49F0C7BAFAC4702756AA1D63B5807FA4BBFBEDDF0BC85CA16B425099FF965634827F928066B3AA45C5CC0F0F62EB85BC0E9A0AD044CB233B0AEE273A197507CDB67E4B7EA40D2EBD14A78B2B02B05F51C8488A065E2BE6B5FD6668FE7E9E93DB79AD902D5E91592629550EAFC1CC189E52A9AAEDBB90568DC2D2FE9EB802BABF68A66A7421B7FBDC1C696339A32803455
| t20$

Es kommt leider nicht 1 heraus!

| t20$ ( echo -n 'scale=0;obase=16;ibase=16;(10001 * ' && (cat d | tr -d '\012') && echo -n ') % ' && cat phiN ) | bc
| 403C060EB9A492036C2B63D57BE049607AD1C3662CDE59702058FCDAA18446BFAFD3\
| B6DD44F8539A2115B09107922DD4A1E3028022A5F19CC7A0FC6CB9D5F30DA28425DA\
| 036DDF23A8008081B9549DED03A9A5DB5FEF0B413B6B6D9E03665BBAB99B2ADF1AF5\
| 460FB30308950E2665A544DACD665A5CC35519CE17892F5171ED67CF1631BE0D358B\
| 3B1EA680962153A6771B95A9EF224D6DDC05BEB1155420E180E11B1EB1C1A7372096\
| EDDAD692F5DEF19584729D01F7CC8F455AAC93743FF1D641FF49656FCF1F6EE81B4F\
| A9F2359E07E67AB78F0CEC5D5ACD0E0B4B67E1304B4BA5AD88617E0EDEE32C7B2995\
| FE8384EA8908881EDD1DD4D596A1686EDC8B9ED97226C401B9AB7749BC4588640067\
| DA7A52B9D9688820C4C3C1BB393265A24A13FE5B8FF48A28FCF368DDAEFA275A8BB7\
| 0493EA32D719773385D5E89A1913AB7CAE21B1B601F2C4A6BA3383CEB1310ED61DB6\
| 3BF8673A0E5F0B60A083DD7846D8CB146A4D3ACB1E21C92F0EF116A48E192684A75D\
| 3D61B462BDDA5B7C5AAD
| t20$

Grmpf.

Muß ich mir noch mal ansehen. Vielleicht ist phiN schon flasch.

Marcel 1iakk (1649300)
--
╭───────╮ ╭──╮ ╭───╮ ╭─╮
╭──╯ ╰────╮ ╭──╮ ╭──╯ ╰─────╮ ╭─╯ ╰───╮ ╭─╯ │ ╭─────╮
─╮ ╰───────────╮ │ │ │ │ ╭────────╯ ╰─╮ ╰─╯ ╰──╮ │ ╰─
╰──────────────╯ ╰─╯ ╰──╯ ╰─────────────╯ ╰─╯ 295901

Marcel Logen

unread,
Apr 28, 2022, 7:44:34 PM4/28/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:
>>Marcel Logen in de.test:

>>>Jetzt könnte man noch die Berechnungen aus den Punkten 1 bis 5 aus
>>><https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
>>>durchführen.
>>
>>Punkt 3:
>
>[...]
>
>phiN = (p-1) * (q-1)
>
>>| t20$ ( ( echo -n 'obase=16;ibase=16;(' && (cat p | tr -d '\012') && echo -n '-1)*(' && (cat q | tr -d '\012') && echo '-1)' ) | bc | tr -d '\\\012' && echo ) > phiN

[...]

>Punkt 5:
>
>(e * d) mod phiN = 1
>
>Klappt aber nicht:

[...]

>Es kommt leider nicht 1 heraus!

[...]

>Grmpf.
>
>Muß ich mir noch mal ansehen. Vielleicht ist phiN schon flasch.

Ah, da kommt mir wieder in den Sinn, noch mal in der englischen
Wikipedia nachzuschauen!

<https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation>

Dort der Punkt 3: Also lambdaN statt phiN. lambdaN = lcm(p-1,q-1).
lcm = least common multiple, kleinstes gemeinsamen Vielfaches (kgV).

Das war es, glaube ich. Hatte ich schon mal vor einiger Zeit.

Na ja, "zu einem späteren Zeitpunkt" dann ... :-)

Marcel 1ib1b (1649707)
--
╰──╮ ╭───╮ ╭─────────╮ ╭─────╮ ╭───────╮ ╭─╮
╰───╯ ╰───╮ ╰──────╮ ╰─╮ ╰─╮ ╰───╮ ╰────╮ ╰─╯ ╰──╮ ╭─╮ ╭─╮
╰───╮ ╭───╯ ╭─╯ ╭──╯ ╭──╯ ╭───╯ ╰──╯ ╰──╯ │
╰─╯ ╰───╯ ╰──────╯ 935d25 │

Marcel Logen

unread,
Apr 29, 2022, 7:04:13 AM4/29/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:

>>phiN = (p-1) * (q-1)
>>
>>>| t20$ ( ( echo -n 'obase=16;ibase=16;(' && (cat p | tr -d '\012') && echo -n '-1)*(' && (cat q | tr -d '\012') && echo '-1)' ) | bc | tr -d '\\\012' && echo ) > phiN
>
>[...]
>
>>Punkt 5:
>>
>>(e * d) mod phiN = 1
>>
>>Klappt aber nicht:
>
>[...]
>
>>Es kommt leider nicht 1 heraus!
>
>[...]
>
>>Grmpf.
>>
>>Muß ich mir noch mal ansehen. Vielleicht ist phiN schon flasch.
>
>Ah, da kommt mir wieder in den Sinn, noch mal in der englischen
>Wikipedia nachzuschauen!
>
><https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation>
>
>Dort der Punkt 3: Also lambdaN statt phiN. lambdaN = lcm(p-1,q-1).
>lcm = least common multiple, kleinstes gemeinsamen Vielfaches (kgV).
>
>Das war es, glaube ich. Hatte ich schon mal vor einiger Zeit.

Ich hatte es gestern nacht noch gelöst. Dazu mußte ich mit dem
euklidischen Algorithmus den ggT von p-1 und q-1 ermitteln, der
war hier 6.

Dann phiN durch diese 6 teilen, um das kgV (lcm) von p-1 und q-1
zu erhalten. also lambdaN. Danach klappte es auch mit

(e * d) mod lambdaN = 1

>Na ja, "zu einem späteren Zeitpunkt" dann ... :-)

Ich poste das noch im einzelnen. (Hatte mir damals mal ein Tool
für den euklidischen Algorithmus (bzw. ggT) geschrieben, aber ich
dachte, die Benutzung desselben könnte ich hier vermeiden.)

BTW: Den de.wikipedia-Eintrag sollte man diesbezüglich mal 'kor-
rigieren'/umschreiben/ergänzen. Denn zumindest GnuPG macht das hier
mit dem lcm. Ob OpenSSL auch, wäre zu prüfen ...

Marcel 1jr40 (1698944)
--
╭─╮ ╭─╮ ╭───╮ ╭────────╮ ╭───────╮ ╭────╮ ╭─╮
╯ │ │ ╰───╯ ╰──╮ ╭──╯ ╭─────╯ ╰─────╮ ╰──╮ ╭──╯ ╭─╯ ╭──╯ ╰──╮
│ ╰───╮ ╰─╯ ╰───────╮ ╭───╯ ╰──╮ ╰──╮ ╰─╮ ╰─────╮ ╰
╰──────╯ ╰──╯ cbf84e ╰─────╯ ╰────────╯

Marcel Logen

unread,
Apr 29, 2022, 8:33:41 PM4/29/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:
>>Marcel Logen in de.test:

>>>phiN = (p-1) * (q-1)
>>>
>>>>| t20$ ( ( echo -n 'obase=16;ibase=16;(' && (cat p | tr -d '\012') && echo -n '-1)*(' && (cat q | tr -d '\012') && echo '-1)' ) | bc | tr -d '\\\012' && echo ) > phiN

[...]

>>Ah, da kommt mir wieder in den Sinn, noch mal in der englischen
>>Wikipedia nachzuschauen!
>>
>><https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation>
>>
>>Dort der Punkt 3: Also lambdaN statt phiN. lambdaN = lcm(p-1,q-1).
>>lcm = least common multiple, kleinstes gemeinsamen Vielfaches (kgV).
>>
>>Das war es, glaube ich. Hatte ich schon mal vor einiger Zeit.
>
>Ich hatte es gestern nacht noch gelöst. Dazu mußte ich mit dem
>euklidischen Algorithmus den ggT von p-1 und q-1 ermitteln, der
>war hier 6.

| t20$ bc -e "obase=16;ibase=16;a[0]=$( cat p|tr -d '\012' && echo -n '-1' );b[0]=$( cat q|tr -d '\012' && echo -n '-1' )" /home/user20/ybtra-t20/rsa-bc-euklid-algo-dezimal
[...]
| ggT(D4CE8501AF0ABFE60A82B15E4F6DC17E15B6CF3BD5A5B68E796FCE396DDF6B6CA614\
| 277BBF4C8EF54A6F465558D634F42BEDA63A50AC8AC3B2F54632641531A2AA0AB52A\
| D94640B5B6B3C7889290E14A35506DB641C1758CCD9CB190EABBCD1D49ABEC8F05F7\
| EDD413A2DE8F54FEBCFB41612E4659A289E2FAF01CD66B31CA64156BF3907915310E\
| 4B86C4777744C59C6E434E44D1C05061D0701DD45757B86209B42F34E79083E6EF27\
| 66ADB465D83A0DD2BE801F98D7FDA9911108892F802A,E7D0FAA5E681C4C17140B2610C1ECB789561EF9DB1892708F389B86057640398342F\
| 8FB2ABF2790D5B81D8A1FAE421EEAC74C80763A6530800FC97948F9D5502FD24B2D3\
| 5E5CC414EB1F031DF9E50BCAB79061FB6783E5ABFE51AB531DA94C3E8E972FA4AA5C\
| 26D3C957020162ED068A1DC90C2B22D2145AC97680B874C1A629BBA38A03ABF311A3\
| D66F9F7083BE0971F21E433B2532406E42916218C1C61DF7EF73AA3841F23C9A6684\
| 1E8F1E86A8A25B968FE1112BBBB475984953DA66867A)=6
[...]

>Dann phiN durch diese 6 teilen, um das kgV (lcm) von p-1 und q-1
>zu erhalten. also lambdaN. Danach klappte es auch mit
>
> (e * d) mod lambdaN = 1
>
>>Na ja, "zu einem späteren Zeitpunkt" dann ... :-)
>
>Ich poste das noch im einzelnen. (Hatte mir damals mal ein Tool
>für den euklidischen Algorithmus (bzw. ggT) geschrieben, aber ich
>dachte, die Benutzung desselben könnte ich hier vermeiden.)

| t20$ cat phiN
| C0B4122C2CEDB60A44822B8073A0DC2170754A32869B0C50610AF68FE48CD43F0F7B2497CEE8FACE634111B316B6897DE5A9078067F1D4D656E2F5462D81D928E78C718E0A499D6AF80181852BFDD9C70AFCF1921FCD21C3B24248DA0A3313302CD1809D50DFD22F190919BF2A7330EFCE9068330F1649FF4D6A469B8DF455C8376D42953A27A0A1B15BF381C263FAF36552C0FDCD66E84994113C133FFC62A482A3515C1544F5A561C4C99083B8E19CD4C08D57D705E765ADD01005BA5CBFD582C5FDDC304F6D5E4CB851EEFDD6A0DA17B37026AD26C51810672A21E237A390E1E2F10899247A2C9CA985717CC1FB8A8EBF9B19985C97597E80C3E4394C95A2DC8C56744C052D0265DD34D0992C01378F6EF82D8C3998624E4B4531AB9730E6DE3BFB12AFDD9E7AF6DA3A990CEE760FA3250DBBBE98854C659A9181B9CE4B3B02760A65152205D84DF42E9A8B6C13932C825922B3E935AE2B1D2221E18B9868D48A613D3EE7B0615A655B8D2CD343EDAA4B738DF617B8251D28398F12751004
| t20$

| t20$ ( ( echo -n 'obase=16;ibase=16;' && cat phiN | tr -d '\012' && echo '/6' )|bc|tr -d '\\\012' && echo ) > lambdaN

| t20$ cat lambdaN
| 201E03075CD24901B615B1EABDF024B03D68E1B3166F2CB8102C7E6D50C2235FD7E9DB6EA27C29CD108AD84883C916EA50F181401152F8CE63D07E365CEAF986D14212ED01B6EF91D4004040DCAA4EF681D4D2EDAFF785A09DB5B6CF01B32DDD5CCD956F8D7AA307D981844A871332D2A26D66B32D2E61AA8CE70BC497A8B8F6B3E78B18DF069AC59D8F53404B10A9D33B8DCAD4F79126B6EE02DF588AAA1070C0708D8F58E0D39B904B76ED6B497AEF78CAC2394E80FBE647A2AD5649BA1FF8EB20FFA4B2B7E78FB7740DA7D4F91ACF03F33D5BC786762EAD668705A5B3F09825A5D2D6C430BF076F71963D94CAFF41C2754484440F6E8EEA6ACB50B4376E45CF6CB9136200DCD5BBA4DE22C4320033ED3D295CECB444106261E0DD9C9932D12509FF2DC7FA45147E79B46ED77D13AD45DB8249F5196B8CBB99C2EAF44D0C89D5BE5710D8DB00F962535D19C1E75898876B0EDB1DFC339D072F85B05041EEBC236C658A35269D658F10E49787788B52470C934253AE9EB0DA315EED2DBE2D56
| t20$

| t20$ ( echo -n 'scale=0;obase=16;ibase=16;(10001 *' && cat d | tr -d '\012' && echo -n ') % ' && cat lambdaN )|bc
| 1
| t20$

Es kommt also 1 heraus.

>BTW: Den de.wikipedia-Eintrag sollte man diesbezüglich mal 'kor-
>rigieren'/umschreiben/ergänzen. Denn zumindest GnuPG macht das hier
>mit dem lcm. Ob OpenSSL auch, wäre zu prüfen ...

Ja, OpenSSL. Später.

Marcel 1jss7 (1700743)
--
╭──────╮ ╭─────╮ ╭──────────╮ ╭─╮ ╭─╮ ╭──╮ ╭─╮
╰───╮ ╰─╮ ╭─╯ ╭──╯ ╰───╮ ╰─╯ │ ╭──╯ ╰───╯ ╰──╮ ╭──╯ ╰──╮
╰─╮ │ ╭──╮ │ ╰──╮ ╭────╯ ╰─╯ ╰─╯ │
╭──────╯ ╰─╯ ╰──╯ ╰─╯ e55b9e ╰

Marcel Logen

unread,
Apr 29, 2022, 8:41:31 PM4/29/22
to
Marcel Logen in de.test:

>e = 65537 = 0x10001

[...]

>phiN / e ist nicht ganzzahlig, d. h. e und phiN sind teilerfremd:

Mein Euklid-Tool sagt dazu:

| ggT(10001,C0B4122C2CEDB60A44822B8073A0DC2170754A32869B0C50610AF68FE48CD43F0F7B\
| 2497CEE8FACE634111B316B6897DE5A9078067F1D4D656E2F5462D81D928E78C718E\
| 0A499D6AF80181852BFDD9C70AFCF1921FCD21C3B24248DA0A3313302CD1809D50DF\
| D22F190919BF2A7330EFCE9068330F1649FF4D6A469B8DF455C8376D42953A27A0A1\
| B15BF381C263FAF36552C0FDCD66E84994113C133FFC62A482A3515C1544F5A561C4\
| C99083B8E19CD4C08D57D705E765ADD01005BA5CBFD582C5FDDC304F6D5E4CB851EE\
| FDD6A0DA17B37026AD26C51810672A21E237A390E1E2F10899247A2C9CA985717CC1\
| FB8A8EBF9B19985C97597E80C3E4394C95A2DC8C56744C052D0265DD34D0992C0137\
| 8F6EF82D8C3998624E4B4531AB9730E6DE3BFB12AFDD9E7AF6DA3A990CEE760FA325\
| 0DBBBE98854C659A9181B9CE4B3B02760A65152205D84DF42E9A8B6C13932C825922\
| B3E935AE2B1D2221E18B9868D48A613D3EE7B0615A655B8D2CD343EDAA4B738DF617\
| B8251D28398F12751004)=1

Und:

| t20$ bc -e "obase=16;ibase=16;a[0]=10001;b[0]=$( cat lambdaN )" /home/user20/ybtra-t20/rsa-bc-euklid-algo-dezimal
[...]
| ggT(10001,201E03075CD24901B615B1EABDF024B03D68E1B3166F2CB8102C7E6D50C2235FD7E9\
| DB6EA27C29CD108AD84883C916EA50F181401152F8CE63D07E365CEAF986D14212ED\
| 01B6EF91D4004040DCAA4EF681D4D2EDAFF785A09DB5B6CF01B32DDD5CCD956F8D7A\
| A307D981844A871332D2A26D66B32D2E61AA8CE70BC497A8B8F6B3E78B18DF069AC5\
| 9D8F53404B10A9D33B8DCAD4F79126B6EE02DF588AAA1070C0708D8F58E0D39B904B\
| 76ED6B497AEF78CAC2394E80FBE647A2AD5649BA1FF8EB20FFA4B2B7E78FB7740DA7\
| D4F91ACF03F33D5BC786762EAD668705A5B3F09825A5D2D6C430BF076F71963D94CA\
| FF41C2754484440F6E8EEA6ACB50B4376E45CF6CB9136200DCD5BBA4DE22C4320033\
| ED3D295CECB444106261E0DD9C9932D12509FF2DC7FA45147E79B46ED77D13AD45DB\
| 8249F5196B8CBB99C2EAF44D0C89D5BE5710D8DB00F962535D19C1E75898876B0EDB\
| 1DFC339D072F85B05041EEBC236C658A35269D658F10E49787788B52470C934253AE\
| 9EB0DA315EED2DBE2D56)=1

Marcel 1jsvd (1700845)
--
╭────╮ ╭─╮ ╭───────╮ ╭────╮ ╭─────────╮ ╭────────╮
╭─╯ ╭─╯ ╭─╮ │ ╰───╯ ╭────╯ ╰─╮ ╰───────╮ ╰───────╮ ╰─╮ ╰──────╮ ╰
╯ ╭─╯ │ │ │ │ ╭───────╯ ╰─╮ ╭─╮ ╭─╯ │ ╭────╮ │
╰─────╯ ╰─╯ ╰─╯ 77b8ae ╰─╯ ╰───╯ ╰─╯ ╰──╯

Marcel Logen

unread,
Apr 29, 2022, 9:08:16 PM4/29/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:

>>rigieren'/umschreiben/ergänzen. Denn zumindest GnuPG macht das hier
>>mit dem lcm. Ob OpenSSL auch, wäre zu prüfen ...
>
>Ja, OpenSSL. Später.

Ich habe hier auf diesem Rechner ja LibreSSL. Dazu hatte ich mir mal
folgende Befehle etc. notiert:

| <https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels>
| <https://de.wikipedia.org/wiki/RSA-Kryptosystem#RSA_mit_dem_Chinesischen_Restsatz>
|
| <https://en.wikipedia.org/wiki/RSA_(cryptosystem)>
|
| cd /tmp
|
| LibreSSL:
| openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:4096 -text -out test-prkey
|
| chmod 600 test-prkey
| less test-prkey
| sed -n -e '/prime1:/,/prime2:/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F > test-prime1
| sed -n -e '/prime2:/,/expo/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F > test-prime2
| sed -n -e '/modulus:/,/publ/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F | sed -e 's/^00//' > test-modulus1
| echo "obase=16;ibase=16;$(cat test-prime1)*$(cat test-prime2)" | bc | tr -d '\\\012\015' > test-modulus2
| cmp test-modulus[12]
| ls -l test-modulus*
| (1024 / 2) * 8 = 512 * 8 = 4096
|
| e = 0x10001 = 65537
| sed -n -e '/private/,/prime1:/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F > test-d
|
| e * d = 1 mod phi(N)
| (e * d) mod phi(N) = 1
| echo "obase=16;ibase=16;($(cat test-prime1)-1)*($(cat test-prime2)-1)" | bc | tr -d '\\\012\015' > test-phi
| echo "scale=0;ibase=16;($(cat test-d)*10001)%$(cat test-phi)" | bc
|
| Chines. Restsatz:
| echo "scale=0;obase=16;ibase=16;($(cat test-d))%($(cat test-prime1)-1)" | bc > test-dp
| echo "scale=0;obase=16;ibase=16;($(cat test-d))%($(cat test-prime2)-1)" | bc > test-dq
|
| sed -n -e '/coefficient:/,$p' test-prkey | sed -e '1d' | tr -d ' :\012\015' | tr a-f A-F > test-qinv
| (qinv * q) mod p = 1
| echo "scale=0;obase=16;ibase=16;($(cat test-qinv)*$(cat test-prime2))%$(cat test-prime1)" | bc

Das kann ich ja in den nächsten Tagen mal durchgehen.

Es sieht mir auf den ersten Blick so aus, als würde LibreSSL nicht
mit lambda, sondern mit phi arbeiten.

Marcel 1kod4 (1728932)
--
╰─────╮ ╭─╮ ╭─╮ ╭──╮
╰─╯ ╰──╮ ╭─╯ │ ╭────────────╮ ╭────╯ │
│ ╰─╮ │ ╭─╮ ╭──╮ ╭───╯ ╭──────╯ │ ╭────╯
╰──────╯ ╰──────╯ ╰───╯ ╰───╯ f7fce4 ╰────────╯ ╰───────

Marcel Logen

unread,
May 2, 2022, 8:58:39 AM5/2/22
to
Marcel Logen in de.test:

>| less test-prkey
>| sed -n -e '/prime1:/,/prime2:/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F > test-prime1
>| sed -n -e '/prime2:/,/expo/p' test-prkey | sed -e '1d;$d' | tr -d ' :\012\015' | tr a-f A-F > test-prime2

Wo wir gerade bei Primzahlen sind.

Freunde von mir haben mich darauf aufmerksam gemacht:

<https://www.spiegel.de/karriere/zaubern-mit-primzahlen-raetsel-der-woche-a-52fbebb8-6aa2-4090-9b21-6add801c4cc2>

Marcel 1olil (1857109)
--
╭────╮ ╭────╮ ╭─╮ ╭──╮ ╭──────╮ ╭─────╮
╯ ╭─╯ ╰─╮ ╰─╮ │ ╰──╯ ╰─╮ ╭───╮ ╰────╮ ╰─╯ ╭──╯ ╭──╮ ╭─╮
╭─╯ ╭─╮ ╭─╯ ╭─╯ │ │ │ ╰──╮ ╭─╯ ╰────╮ ╭─╯ ╰─╯ │
╰────╯ ╰─╯ ╰────╯ ╰──╯ ╰──╯ ╰───╯ 9a90e6 ╰─

Marcel Logen

unread,
May 2, 2022, 11:22:50 AM5/2/22
to
Marcel Logen in de.test:

>Wo wir gerade bei Primzahlen sind.
>
>Freunde von mir haben mich darauf aufmerksam gemacht:
>
><https://www.spiegel.de/karriere/zaubern-mit-primzahlen-raetsel-der-woche-a-52fbebb8-6aa2-4090-9b21-6add801c4cc2>

Ich habe mit LibreSSL mal folgenden Testkey (4096 Bit) erzeugt:

| RSA Private-Key: (4096 bit)
| modulus:
| 00:c9:a6:53:7a:bc:cd:ba:2f:a2:94:8d:62:00:80:
| 51:5e:d9:6d:d4:34:04:33:95:fa:82:f4:36:e0:57:
| 7b:09:63:4e:23:34:3c:c4:b5:51:59:b5:08:04:e6:
| 55:5c:f9:b0:c4:a9:52:cd:60:b8:3a:32:9b:b3:3f:
| 79:50:60:02:52:d9:90:ff:cd:65:58:50:38:38:cb:
| 00:89:5b:07:cc:e7:04:bb:3c:60:08:96:1e:f5:8e:
| 2d:14:50:dd:47:1d:1a:68:a5:62:44:d0:51:cc:06:
| 58:53:ba:45:97:eb:63:b7:ff:e4:52:b9:6b:40:11:
| a3:c2:99:ab:7f:a5:52:2a:5c:09:ea:f3:80:60:04:
| 3b:7d:c4:e4:dc:ca:a4:ba:b9:bb:c6:9d:0e:e8:89:
| d2:7e:10:03:3c:f9:30:59:1f:77:b9:90:48:dc:1b:
| 9d:0c:98:04:94:c9:38:bf:c6:cb:58:56:bc:76:e4:
| 92:2e:60:61:bb:56:96:4e:08:4e:00:fb:a0:e8:96:
| 2e:d3:46:5a:f8:fe:eb:c9:8e:dc:63:db:4c:7b:37:
| ad:07:91:75:23:fd:90:27:52:5e:c0:20:2f:7f:f2:
| c3:8f:18:ec:59:f1:cd:ea:52:f7:53:36:9b:64:c4:
| 8c:61:0e:e8:06:57:cd:c9:a6:bb:32:b1:69:d5:fd:
| 97:c6:5d:d7:2c:8c:58:16:04:3b:f0:cc:49:bd:45:
| cd:a4:d9:f7:1e:9e:86:b7:97:68:18:de:fa:36:1d:
| 29:66:6f:66:16:72:07:6a:0f:b4:de:10:3e:33:44:
| 12:cf:aa:47:b7:9e:37:c1:f8:1b:fb:56:46:c4:ab:
| d3:6b:d5:56:0e:ae:34:15:9e:9f:5b:f0:82:0e:1a:
| 87:1d:04:52:e1:cc:ca:11:5f:47:97:c2:74:89:f9:
| d9:ba:c0:d7:c9:d8:62:28:ae:b0:2a:1e:53:b1:e0:
| 4e:79:6f:26:a0:db:dc:d8:63:b0:45:68:bb:c1:9c:
| 6b:36:4b:28:9f:c8:f6:e4:25:ce:9c:56:ca:4c:f2:
| e7:93:37:89:c3:1e:74:1b:51:29:2a:80:11:d3:fd:
| 18:4c:29:c9:3a:2f:d8:4d:78:17:f1:c4:5a:b6:b4:
| aa:b6:98:2a:e3:30:0d:c7:8a:d1:db:b3:df:9f:54:
| 97:e0:e0:87:7d:7a:de:a0:ca:85:db:3e:6a:63:8f:
| 6e:42:ac:e9:07:6c:df:cc:74:79:2a:b8:ed:27:69:
| 63:ff:a0:6c:6c:57:be:d6:e7:20:87:a7:81:64:4f:
| f2:01:2a:42:1b:d8:2b:ec:91:82:49:2b:6e:27:08:
| fa:c4:3c:a9:07:f6:7e:5e:85:9d:e2:38:17:c1:5c:
| c9:aa:95
| publicExponent: 65537 (0x10001)
| privateExponent:
| 72:96:12:4f:e7:a3:dc:0e:1f:8b:dc:bf:78:db:71:
| e1:bd:1a:3d:00:85:f6:ae:5e:19:36:1f:4c:e2:49:
| 27:2f:88:02:57:37:c4:eb:e7:db:5b:14:c0:7c:06:
| bb:fb:a3:28:4d:b3:a0:c3:3a:4c:cf:df:4c:3f:60:
| 77:7c:e7:35:1f:2e:d7:3d:67:3e:84:ef:3d:ce:95:
| 72:78:08:f9:b5:b9:29:90:88:5d:b8:b8:c4:fe:d2:
| bc:fd:aa:90:33:88:83:38:9f:9b:cc:e8:fe:50:08:
| b7:23:5d:52:93:cf:29:8a:be:bb:07:64:5b:96:ea:
| 80:b5:84:0f:d7:e8:d5:eb:51:33:72:c5:5b:4a:6c:
| 67:ee:8f:c2:ab:60:6a:3f:0a:e6:34:ef:78:d2:80:
| 8b:64:1c:02:f4:f3:35:61:bd:4d:f4:20:82:fb:2a:
| 06:33:08:3f:68:0c:d8:65:65:bd:c0:23:fe:47:aa:
| 8d:b1:f5:37:58:5f:b6:dd:df:3d:8d:bf:85:0b:7a:
| 76:52:3f:75:c8:9e:41:fd:ed:5c:cd:0c:2b:e4:9a:
| 6d:77:89:a2:36:ff:48:68:f5:30:a5:d9:78:12:82:
| 6f:f9:50:ad:57:cb:94:41:2b:0b:dd:36:f6:4e:fe:
| 1a:55:37:22:0b:99:03:e2:bb:f3:75:7f:57:bb:70:
| 17:a4:28:cc:2a:e8:2d:5f:b2:22:16:df:1c:23:c6:
| 0c:9f:7d:95:05:56:d0:4d:84:29:ec:68:1f:74:7c:
| 12:1d:32:42:60:8c:b1:e0:db:14:d7:c7:08:7c:52:
| bf:99:38:ba:ca:a9:04:4c:b0:5c:ee:66:e1:4b:f1:
| c1:89:ef:92:18:fd:e7:ae:74:4e:ba:0a:d4:f5:74:
| 84:f3:b9:c7:68:31:5e:87:8d:4d:2f:df:d7:3e:a4:
| dc:45:59:3a:7b:b6:b9:8c:f2:80:1d:93:30:9f:6b:
| 5a:73:41:be:39:42:03:8b:bd:70:0f:19:2b:3a:0b:
| 8d:21:bc:e8:5b:21:8e:11:71:f7:59:34:54:d1:ab:
| c2:de:bf:df:84:e9:cb:e2:4b:05:b0:cf:01:6b:cc:
| de:85:f1:d2:8d:ed:9c:48:90:13:e7:fe:91:69:26:
| b1:55:ef:44:e3:86:5d:a1:b4:ec:40:88:61:9b:b3:
| 38:cf:24:48:a0:21:45:64:94:47:93:13:c1:17:d7:
| d1:db:c9:3d:6c:81:9c:49:bc:1a:98:16:e2:71:80:
| 5d:39:83:af:8f:b7:16:60:66:63:c1:04:e6:45:06:
| 6f:58:31:e1:88:3c:3d:c9:9e:a2:0b:d0:a8:4f:70:
| 2f:75:ff:3f:a6:6d:9e:f8:af:4e:c3:22:67:39:14:
| f4:cd
| prime1:
| 00:fc:7e:3d:06:c5:85:53:70:f4:4c:5a:ae:9c:4e:
| e8:16:81:7a:e6:33:fd:cb:94:57:df:58:41:54:93:
| eb:d0:7e:cf:24:3e:03:70:97:3c:66:7f:02:8f:6e:
| 0d:c4:50:7d:f1:75:c9:bd:42:2e:dd:89:f1:89:3d:
| a9:5f:81:49:59:b8:a6:ff:3d:85:6f:d8:26:71:53:
| fb:4b:29:c8:a4:99:b3:0f:34:5a:fb:e3:d7:65:4d:
| fe:d6:ea:4e:6a:53:e0:1a:af:7a:70:c2:2d:14:af:
| 85:7d:a0:a2:4f:bf:33:93:04:2e:20:cd:a0:0c:0e:
| 29:b2:31:a4:7c:c4:d8:d1:77:36:4d:44:94:6f:ff:
| 67:b7:27:4c:64:7c:11:e4:d8:61:1e:15:5b:73:53:
| 26:14:cc:45:fa:2d:c9:f7:34:2d:0a:60:e9:f0:f1:
| 95:c0:1e:11:94:3f:39:41:37:db:16:af:8e:e3:37:
| 08:17:dd:f7:0b:fc:24:83:94:02:aa:6a:a7:bf:28:
| bb:ad:b0:7a:c6:17:8d:63:18:36:02:0f:87:c5:47:
| ab:a4:7c:47:c6:af:26:2a:16:b6:f6:20:51:1e:6a:
| 6e:f8:19:6d:96:41:26:88:d4:ef:f5:d3:7d:da:7e:
| a6:d3:f8:96:8b:e6:4e:08:e7:e3:20:32:79:d9:1b:
| 75:ab
| prime2:
| 00:cc:73:4f:39:c3:18:3f:e5:36:71:1e:60:f9:50:
| fa:f6:c4:48:79:21:59:eb:95:1e:dc:6f:cb:e7:db:
| 8e:88:84:c6:64:f3:bc:5b:e4:ce:15:b3:01:e9:30:
| 1c:50:6a:9d:55:5f:f8:dd:44:bc:4a:a0:8b:ed:52:
| e2:76:27:49:ae:50:3e:7e:86:1a:c9:b6:1d:07:a2:
| 28:fc:d1:55:cd:06:8c:4b:63:5d:3d:b3:69:43:a1:
| 2b:0f:75:01:ce:5a:b0:13:d7:3d:d9:39:59:7f:72:
| dc:f0:39:0e:3b:ef:24:3e:29:e8:e7:81:48:9f:0f:
| d9:f2:63:e6:dc:4c:7c:db:1f:5c:aa:a4:07:58:11:
| f4:41:e2:fc:e0:78:03:9e:e7:2d:e5:cc:cd:d0:31:
| 97:d0:e3:f4:c4:a5:aa:7c:4d:5b:e5:30:b5:2e:68:
| be:de:8c:81:d9:6e:8b:27:03:91:a4:3e:3e:9f:71:
| 6f:ff:ae:a5:e1:27:81:51:20:a8:6a:58:a4:85:15:
| 32:80:b0:16:df:24:a1:20:0b:a3:7e:b6:e4:19:16:
| db:ae:39:fa:3d:62:7e:e5:c4:ed:a8:60:5f:30:0a:
| 37:f0:e3:2a:12:e2:c0:54:4d:b7:b9:cd:87:56:ea:
| 46:13:3b:5b:b0:7e:cc:96:d1:27:33:70:6e:21:46:
| a0:bf
| exponent1:
| 19:f5:98:ac:a3:8e:2b:a0:07:5d:fa:4c:cd:81:47:
| 57:59:04:9b:ba:68:b3:8f:92:e1:41:9f:a5:e4:77:
| 70:3e:39:69:ce:7e:68:0b:04:88:bd:32:34:30:ea:
| 75:6e:99:24:44:29:f3:ad:64:48:1e:b0:98:9d:a0:
| 56:53:62:89:38:f4:e2:75:1e:cc:fa:fa:28:d8:ab:
| 93:74:be:4e:3e:07:2c:df:03:23:b6:af:24:99:3a:
| 44:3a:5e:c9:8b:ca:14:b4:49:f0:61:e6:64:a4:0f:
| 23:75:6a:7a:ac:7b:ce:f7:b5:0e:66:55:b8:27:94:
| 9d:df:80:bb:db:39:37:7f:fc:33:41:83:c9:68:06:
| ef:cb:b8:8c:f4:3c:9a:bc:ac:6f:7d:5e:a3:a2:be:
| dd:90:8a:f9:47:cf:e5:fc:95:4c:e5:dd:e7:89:cf:
| 0d:ab:89:bf:26:28:ea:cd:a5:56:d5:c1:e9:16:75:
| 5c:8e:d3:a1:85:d0:f3:3e:3a:6f:ee:fb:44:2a:19:
| f1:a7:9d:57:d4:80:12:da:20:63:61:d9:61:ad:16:
| b6:98:98:80:92:ed:67:92:62:49:37:d5:5f:3d:2e:
| 1f:8f:ed:b6:6f:08:59:35:1b:5e:b8:d9:cd:a7:0b:
| db:eb:48:ff:25:34:8c:b1:da:a6:2a:ca:60:49:f4:
| 75
| exponent2:
| 1f:df:86:25:62:25:e0:a8:32:41:96:53:d5:ea:6b:
| 05:97:7a:18:f0:3b:1d:80:04:ec:a6:bd:2a:2b:4f:
| 60:37:1a:da:d8:28:b0:46:ce:5e:11:a7:25:9c:6b:
| 7d:99:f1:67:42:ec:00:4a:db:f3:e2:6d:8e:15:12:
| db:0a:aa:f0:f2:ef:9b:37:fa:eb:21:6a:0b:2b:9b:
| aa:36:54:62:ff:37:55:f5:6a:ae:d8:ce:7b:4d:9f:
| f1:eb:f2:d9:21:c8:3b:7f:9d:d3:c4:9e:10:41:6e:
| f2:40:62:d8:b3:22:7a:52:7c:4d:c3:18:f8:3b:37:
| 66:13:6f:05:3f:23:63:e1:d2:c7:83:84:e5:94:fe:
| f8:5a:93:c3:c6:d2:01:ae:d6:b7:f1:a2:d0:67:3a:
| dc:c4:fc:fe:bf:39:01:e1:e9:86:a4:7e:4a:7a:e7:
| ee:b8:06:f2:47:ca:87:cd:85:a2:0e:56:22:f3:43:
| 5b:9f:f5:9a:51:57:56:b7:79:aa:02:a1:bb:61:9f:
| 9a:f2:58:ce:76:de:6b:a9:84:d6:97:5a:9e:12:b3:
| 32:c9:35:1a:e6:c5:13:bb:0c:b5:e8:38:4e:bb:f9:
| 16:a3:c3:86:68:35:45:af:4c:0a:3a:61:74:0a:57:
| dc:5d:af:a0:a7:53:eb:db:35:7a:4e:77:cc:d6:3e:
| ef
| coefficient:
| 00:d8:0b:be:74:74:f6:3f:30:12:b2:e4:e9:6f:a4:
| 17:6e:0f:70:03:66:eb:71:70:0e:12:8c:6f:8d:27:
| 2f:0f:e7:9b:2a:3c:92:00:9c:09:6a:08:00:3e:5a:
| 40:2c:72:24:a7:02:f1:85:80:c3:80:03:30:4d:57:
| df:48:2b:8e:eb:ee:63:d1:c6:36:af:8d:04:74:40:
| df:f1:04:51:63:f4:84:b9:cc:1d:49:31:ca:e3:df:
| ca:ec:6e:4d:68:4d:51:05:ff:31:2d:bf:5a:d6:6d:
| a4:7f:31:d3:83:8e:ba:c4:7b:5b:23:9a:c3:3b:8d:
| 77:45:86:4c:b0:87:71:8c:53:61:84:d7:3e:0b:21:
| dd:1f:38:b6:3b:03:18:c9:b2:be:5d:65:3f:aa:03:
| d0:dd:f7:49:41:a5:61:09:e5:c9:69:30:72:fc:78:
| ec:a7:5a:6b:17:62:c4:af:7e:a6:c9:5d:40:c2:ca:
| 12:86:c3:eb:ee:a0:18:14:c4:2c:f7:1f:38:62:f7:
| e1:01:49:f0:3a:d2:d4:39:36:84:23:1f:a3:bb:c2:
| 32:f0:70:66:b4:f5:0c:2c:ae:26:8d:98:67:58:4f:
| d4:a6:0e:a1:75:e6:5a:b9:46:99:a2:c2:4d:7c:14:
| dc:07:6a:c0:98:16:5e:e1:f0:08:d2:ab:5c:47:96:
| 65:5c

Dann habe ich die Primzahlen "prime1" und "prime2" in je eine
Datei gespeichert. Anschließend den SPIEGEL-ONLINE-Test gemacht:

| t20$ echo "scale=0;ibase=16;((" $(cat test-prime1) '^2)-1) % 18' | bc
| 0
| t20$ echo "scale=0;ibase=16;((" $(cat test-prime2) '^2)-1) % 18' | bc
| 0
| t20$

Man beachte, daß dezimal 24 = 0x18 (wegen "input base = 16").

Marcel 1nstj (1831859)
--
╰──╮ ╭─╮ ╭──────╮ ╭────╮ ╭───╮
╭─╯ ╭──────╮ │ │ ╰───╮ │ ╰──╮ ╰─╯ ╰─╮
╰─╮ ╭─────╯ ╭──╯ ╭─╯ ╰─╮ ╭─╮ │ │ ╭─╮ ╭──╮ │ ╭──────╯ ╭─
╰────────────╯ 94b8dd ╰────╯ ╰─╯ ╰─╯ ╰─╯ ╰─╯ ╰─╯ ╰─────────╯

Marcel Logen

unread,
May 2, 2022, 4:02:05 PM5/2/22
to
Marcel Logen in de.test:

>Ich habe mit LibreSSL mal folgenden Testkey (4096 Bit) erzeugt:
>
>| RSA Private-Key: (4096 bit)
>| modulus:
>| 00:c9:a6:53:7a:bc:cd:ba:2f:a2:94:8d:62:00:80:
>| 51:5e:d9:6d:d4:34:04:33:95:fa:82:f4:36:e0:57:
>| 7b:09:63:4e:23:34:3c:c4:b5:51:59:b5:08:04:e6:
[...]
>| f2:01:2a:42:1b:d8:2b:ec:91:82:49:2b:6e:27:08:
>| fa:c4:3c:a9:07:f6:7e:5e:85:9d:e2:38:17:c1:5c:
>| c9:aa:95
>| publicExponent: 65537 (0x10001)
[...]
>| prime1:
>| 00:fc:7e:3d:06:c5:85:53:70:f4:4c:5a:ae:9c:4e:
>| e8:16:81:7a:e6:33:fd:cb:94:57:df:58:41:54:93:
>| eb:d0:7e:cf:24:3e:03:70:97:3c:66:7f:02:8f:6e:
[...]
>| 6e:f8:19:6d:96:41:26:88:d4:ef:f5:d3:7d:da:7e:
>| a6:d3:f8:96:8b:e6:4e:08:e7:e3:20:32:79:d9:1b:
>| 75:ab
>| prime2:
>| 00:cc:73:4f:39:c3:18:3f:e5:36:71:1e:60:f9:50:
>| fa:f6:c4:48:79:21:59:eb:95:1e:dc:6f:cb:e7:db:
>| 8e:88:84:c6:64:f3:bc:5b:e4:ce:15:b3:01:e9:30:
[...]
>| db:ae:39:fa:3d:62:7e:e5:c4:ed:a8:60:5f:30:0a:
>| 37:f0:e3:2a:12:e2:c0:54:4d:b7:b9:cd:87:56:ea:
>| 46:13:3b:5b:b0:7e:cc:96:d1:27:33:70:6e:21:46:
>| a0:bf
>| exponent1:
[...]

Der Modulus ist jedenfalls schon mal das Produkt aus prime1 und
prime2.

Marcel 1o7i4 (1842756)
--
╰──────────────╮ ╭────────────╮ ╭───────╮ ╭─╮ ╭──╮
╰───╯ ╭─────────╯ ╭───╮ ╰────╮ ╰──╯ ╰─╯ │
│ ╭─╮ ╭─╮ ╭─╮ ╭─╯ ╰──╮ ╭──╮ │ ╭─────────╯
╰──╯ ╰─╯ ╰─╯ ╰─╯ 235415 ╰───╯ ╰───╯ ╰──────────╮

Marcel Logen

unread,
May 2, 2022, 4:35:50 PM5/2/22
to
Marcel Logen in de.test:

>Marcel Logen in de.test:

>>Ich habe mit LibreSSL mal folgenden Testkey (4096 Bit) erzeugt:
>>
>>| RSA Private-Key: (4096 bit)
>>| modulus:
>>| 00:c9:a6:53:7a:bc:cd:ba:2f:a2:94:8d:62:00:80:
>>| 51:5e:d9:6d:d4:34:04:33:95:fa:82:f4:36:e0:57:
>>| 7b:09:63:4e:23:34:3c:c4:b5:51:59:b5:08:04:e6:
>[...]
>>| f2:01:2a:42:1b:d8:2b:ec:91:82:49:2b:6e:27:08:
>>| fa:c4:3c:a9:07:f6:7e:5e:85:9d:e2:38:17:c1:5c:
>>| c9:aa:95
>>| publicExponent: 65537 (0x10001)

[...]

>Der Modulus ist jedenfalls schon mal das Produkt aus prime1 und
>prime2.

Und es gilt:

0,1 < | ld(prime1) - ld(prime2)| = 0,3045 < 30.

Außerdem sind 65537 (= 0x10001) und phiN teilerfremd:

| ggT(10001,C9A6537ABCCDBA2FA2948D620080515ED96DD434043395FA82F436E0577B09634E23\
| 343CC4B55159B50804E6555CF9B0C4A952CD60B83A329BB33F7950600252D990FFCD\
| 6558503838CB00895B07CCE704BB3C6008961EF58E2D1450DD471D1A68A56244D051\
| CC065853BA4597EB63B7FFE452B96B4011A3C299AB7FA5522A5C09EAF38060043B7D\
| C4E4DCCAA4BAB9BBC69D0EE889D27E10033CF930591F77B99048DC1B9D0C980494C9\
| 38BFC6CB5856BC76E4922E6061BB56964E084E00FBA0E8962ED3465AF8FEEBC98EDC\
| 63DB4C7B37AD07917523FD9027525EC0202F7FF2C38F18EC59F1CDEA52F753369B64\
| C48C610EE80657CDC9A6BB32B169D5FD97C494E5A04BCF7870E5C60ED0ADB02DC1CC\
| B15B3F315FE03EA2233228E0B9EC166280E8D5AA4338D3940C2ECB74A5958C9C5761\
| FF5D95102E1C473542DFFFAD7BA62B3020DBBBB6F3CAA190F8BC57C35B29D204AFDF\
| 88DD4950EA90DA78799FB398802971D4582B4C2C17014CF0502E8092822E606CD8F1\
| 4D32A693146FE58E7938095EE1B12AD6373E7F79D98005CD699B7C2FAAB9938E4418\
| FF7104D9049668D4C917955061F9804FC2600322966EF8F1D1D1EF68C8FAE08DBAFA\
| F5D13029A7174B30547E8875C7A39DF155513826BB8B05784DB62A53AD31D744E309\
| 00B4017D5A4145842F0805B45FA17BCD21D791D7557515BA1943E5E4D7E474D96267\
| 942C)=1

(e * d) mod phiN = 1

| t20$ echo "scale=0;obase=16;ibase=16;(10001*" $(cat test-privateexponent-aus-key ) "%" $(cat test-phi-berechnet )")"|bc
| 1
| t20$

Hier bei LibreSSL wird also offenbar mit phiN statt lambdaN gearbeitet.

Die restlichen Elemente des Keys werden für folgende Berechnungen
benötigt:

<https://de.wikipedia.org/wiki/RSA-Kryptosystem#RSA_mit_dem_Chinesischen_Restsatz>

Marcel 1p699 (1874217)
--
╭─────╮ ╭──╮ ╭───╮ ╭─╮ ╭───────╮ ╭──╮
╰─╮ ╰──╯ │ ╰─╮ │ ╭─╮ ╭─╮ ╭─╯ │ │ ╭────╯ ╭─╯ ╰
─╮ ╭─╯ │ ╭──────╯ ╰─╯ ╰─╯ ╰─╯ │ ╭─╮ ╭──╯ ╰──╮ ╭─╮ │
╰───╯ ╰──╯ ╰─╯ ╰─╯ 674479 ╰──╯ ╰──╯

Marcel Logen

unread,
May 2, 2022, 4:57:28 PM5/2/22
to
Marcel Logen in de.test:

>Hier bei LibreSSL wird also offenbar mit phiN statt lambdaN gearbeitet.
>
>Die restlichen Elemente des Keys werden für folgende Berechnungen
>benötigt:
>
><https://de.wikipedia.org/wiki/RSA-Kryptosystem#RSA_mit_dem_Chinesischen_Restsatz>

"dmp1" und "dmq1" aus der Wikipedia sind "exponent1" und "exponent2"
aus dem LibreSSL-Schlüsselmaterial.

Fehlt noch die Ermittlung von "iqmp" (Wikipedia) bzw. "coefficient"
aus dem Key. Dafür brauche ich wahrscheinlich den erweiterten eukli-
dischen Algorithmus. (Ein Tool liegt mir vor.) Mal sehen.

Marcel 1o9cq (1844634)
--
╭─╮ ╭──╮ ╭──────╮ ╭──╮ ╭─╮ ╭─╮ ╭───╮ ╭───────╯
╯ ╰─╯ ╰──╮ ╰──╮ ╰───╮ ╭─╮ ╭────╯ ╰─╯ │ │ │ ╰─╮ │ ╰────╮
│ ╭─╯ ╰─╯ ╰─╮ ╰───╮ ╰──╯ ╰───────╯ ╰─╮ │
╰───╯ ╰──────╯ 71a0c6 ╰─────╯

Marcel Logen

unread,
May 2, 2022, 5:39:25 PM5/2/22
to
Marcel Logen in de.test:

>><https://de.wikipedia.org/wiki/RSA-Kryptosystem#RSA_mit_dem_Chinesischen_Restsatz>
>
>"dmp1" und "dmq1" aus der Wikipedia sind "exponent1" und "exponent2"
>aus dem LibreSSL-Schlüsselmaterial.
>
>Fehlt noch die Ermittlung von "iqmp" (Wikipedia) bzw. "coefficient"
>aus dem Key. Dafür brauche ich wahrscheinlich den erweiterten eukli-
>dischen Algorithmus. (Ein Tool liegt mir vor.) Mal sehen.

Man kann es auch direkt prüfen:

| t20$ echo "scale=0;obase=16;ibase=16;(" $(cat test-prime2) "*" $(cat test-coeff-aus-key) ")% " $(cat test-prime1)| bc
| 1
| t20$

Dabei sind

test-prime1 = p
test-prime2 = q
test-coeff-aus-key = iqmp (multiplikatives Inverses von q, mod p)

Ich hatte den erweiterten euklidischen Algorithmus bemüht, um iqmp
zu berechnen:

| t20$ bc -e "obase=16;ibase=16;a[0]=$(cat test-prime1);b[0]=$(cat test-prime2)" /home/user20/ybtra-t20/rsa-bc-erw-euklid-algo
[...]
| a[0]=FC7E3D06C5855370F44C5AAE9C4EE816817AE633FDCB9457DF58415493EBD07ECF24\
| 3E0370973C667F028F6E0DC4507DF175C9BD422EDD89F1893DA95F814959B8A6FF3D\
| 856FD8267153FB4B29C8A499B30F345AFBE3D7654DFED6EA4E6A53E01AAF7A70C22D\
| 14AF857DA0A24FBF3393042E20CDA00C0E29B231A47CC4D8D177364D44946FFF67B7\
| 274C647C11E4D8611E155B73532614CC45FA2DC9F7342D0A60E9F0F195C01E11943F\
| 394137DB16AF8EE3370817DDF70BFC24839402AA6AA7BF28BBADB07AC6178D631836\
| 020F87C547ABA47C47C6AF262A16B6F620511E6A6EF8196D96412688D4EFF5D37DDA\
| 7EA6D3F8968BE64E08E7E3203279D91B75AB
| b[0]=CC734F39C3183FE536711E60F950FAF6C448792159EB951EDC6FCBE7DB8E8884C664\
| F3BC5BE4CE15B301E9301C506A9D555FF8DD44BC4AA08BED52E2762749AE503E7E86\
| 1AC9B61D07A228FCD155CD068C4B635D3DB36943A12B0F7501CE5AB013D73DD93959\
| 7F72DCF0390E3BEF243E29E8E781489F0FD9F263E6DC4C7CDB1F5CAAA4075811F441\
| E2FCE078039EE72DE5CCCDD03197D0E3F4C4A5AA7C4D5BE530B52E68BEDE8C81D96E\
| 8B270391A43E3E9F716FFFAEA5E127815120A86A58A485153280B016DF24A1200BA3\
| 7EB6E41916DBAE39FA3D627EE5C4EDA8605F300A37F0E32A12E2C0544DB7B9CD8756\
| EA46133B5BB07ECC96D12733706E2146A0BF
| s[0]=1D832697591C86ED5F00B550D88AB4B7166724926000530880A43134B254F5FCA31F\
| 237A353D851FA08B53915997D57C1CC1B8E9DA40FEE902B33D8B4B3B336CB3FB9F97\
| BD550CE9C978C9F87E89684880DF1412D84DA914768A88020FAF18D018404AF193F8\
| 489917840A851E68AE98C831B06E33F2DA2C76A9C188EDFB3CBF5740077028D5241D\
| 2D8695ECE77CC5E8ED98C07282A491ED8662A1C30D014CDF96920DE1DAFAE002A23A\
| 5F1594E768678808FD8AD3E8D4E3D04D10E1A11C1BF179405498AD0CC33C13D378BC\
| BDDD965FBB8A0EDCCBF4CCE9BCB4233FCDAE88BC1447CC6F3A48B4C787FD350571E2\
| 19FC023D005EEB5D68A8E1C8A7CD34108AD6
| t[0]=-24727E92508F1440E19975C52CAAD0A8720AE2CD125A2449CCCBD1C76CBCC09733F\
| A01716FFB32FC77025113CD97DE594A72D837C16B5D86C13BE5CA1755BA6DCA432D7\
| 74EC04B21FD131B5A257740A52E55683DB2B20C816E33EA7C0102068F14B0494302D\
| 23E41E0FE6ECECC3078CE88D2FD32DCD080B26CAB57CC3D674523D4C86D5664DD8A9\
| 7EE962978F91B25A2C0B01BC94F5536D4FCB88868ED4E63A13076F478A918C3A67CD\
| C7491B9344D524E206CF5911A0B1D5C0C6ECFD5B34B6F5C30DAAC668A8B44B929E1B\
| 1DEEFE4098578B40BE111BA19FD68906887E9C61A9A520ACC205ACBCF8E565311305\
| E69CACC8DD5F3CFEF26F7DA4D871D9185104F
| a[0]*s[0]+b[0]*t[0]=1

Demnach wäre t[0] das multiplikative Inverse zu b[0], mod a[0].
Also t[0] das Inverse zu q, mod p.

Wenn ich zu dem (negativen) t[0] noch p addiere, dann komme ich
genau auf iqmp (= "coefficient" aus dem Key).

Stimmt also alles!
(Jne wn nhpu avpug naqref mh rejnegra. :-)

Marcel 1oaig (1845840)
--
╭───╮ ╭────────╮ ╭──╮
╰─╮ ╰─╮ ╭────────╯ ╭─────╯ ╭─╮ │ ╰─╮ ╭─
──╮ ╭──╮ ╭──╮ │ │ ╰──────╮ ╭─╯ ╭──╮ │ ╰───╮ │ ╰─╯
╰─╯ ╰─╯ ╰──╯ ╰─────────╯ ╰─────────────╯ ╰───╯ ╰───╯ 166ec8

Marcel Logen

unread,
May 3, 2022, 9:22:38 AM5/3/22
to
Marcel Logen in de.test:

>Stimmt also alles!
>(Jne wn nhpu avpug naqref mh rejnegra. :-)

Im Prinzip braucht man also für den RSA-Schlüssel nur "prime1",
"prime2" und den "publicExponent". Der Rest läßt sich daraus be-
rechnen.

Oder: Man wirft die Primzahlen weg und behält N, e und d. Wobei
(N, e) der öffentliche Schlüssel und (N, d) der geheime Schlüssel
sind.

Aus de.wikipedia (Eintrag "RSA-Kryptosystem"):

| Die Zahlen p, q und φ(N) werden nicht mehr benötigt und können
| nach der Schlüsselerstellung gelöscht werden. Es ist jedoch re-
| lativ einfach, diese Werte aus e, d und N zu rekonstruieren.
| p, q, φ(N) und d müssen geheim gehalten werden.

Das Rekonstruieren wäre jetzt noch interessant.

Marcel hu2 (18370)
--
╭──────╮ ╭──╮ ╭──╮ ╭─╮ ╭───────╮
╰─╮ ╭─╯ │ ╰───╯ │ ╭───╯ ╰────╮ ╭──╮ │ ╭───╯ ╭─
╭─╯ ╰────╮ ╭───╯ ╭──────╯ ╭─╯ ╭─────╯ │ │ │ ╰────╮ ╭─╯
╭───╯ ╰───╯ ╰────────╯ ╰───────╯ ╰───╯ 206a1c ╰──╯

Marcel Logen

unread,
May 4, 2022, 10:31:08 AM5/4/22
to
Marcel Logen in de.test:

>Aus de.wikipedia (Eintrag "RSA-Kryptosystem"):
>
>| Die Zahlen p, q und φ(N) werden nicht mehr benötigt und können
>| nach der Schlüsselerstellung gelöscht werden. Es ist jedoch re-
>| lativ einfach, diese Werte aus e, d und N zu rekonstruieren.
>| p, q, φ(N) und d müssen geheim gehalten werden.
>
>Das Rekonstruieren wäre jetzt noch interessant.

Ich habe mir gestern mal ein PDF dazu angesehen (da ging es aller-
dings um die Wiederherstellung eines kaputten RSA-Schlüssels).

Die Rekonstruktion von p und q scheint aber demnach wohl - jeden-
falls nach meinem beschränkten Verständnis - nicht ganz so einfach
zu sein.

Der Versuch der Faktorisierung von N sollte aber (heute noch)
scheitern: Das ist ja gerade der Sinn hinter dem RSA-Verfahren.
Wie sich das dann mit Quantencomputern gestaltet ... Man wird
sehen.

Marcel 2cld (78509)
--
╰─╮ ╭────╮ ╭───╮ ╭──╮ ╭──╮ ╭─╮ ╭─────╮ ╭────────╮
╰───╯ ╰──╮ ╭─╯ │ │ ╰────╯ ╰─╮ ╭─╮ ╭──╯ ╰─╯ ╭──╯ ╰─╮ ╭───╯
╰─╯ ╰─╯ ╰─╮ │ │ ╰────╮ ╰──╮ ╭─╯ │ ╭─
╰─╯ ╰───────╯ 60208b╰──╯ ╰──╯
0 new messages