Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.crypt > #50382

Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

Show all headers | View raw

On 10/2/21 10:34 AM, Peter Pearson wrote:

> Is my description of the encryption and decryption processes wrong?
> I took those two lines straight from the paper, but maybe I missed
> some explanation about how this wasn't the real algorithm.
> 
> If my description of the algorithm is wrong, please present the
> correct algorithm.  
> 
> If my description is correct, please provide sample values for
> e, Sara, and Bra, and I will either tell you what M is, or
> demonstrate that there is no unique decryption of e.
> 

O, snap! Now I must belay this exercise. The system is borked, as you
said, Mr. Pearson. Secret and public values commute like a bus. Here is
a sample output you will probably break fast. Enjoy:

pubkey (Sara, Bra)  :
   57333613759833334679914302455108124,
   320632539812891314264995223041035707802067

ciphertext (e) :
   289609149406663016296773405950344946146989

Even with the exponentiation and addition as specified in the paper the
private base can be recovered from the public raised base modulus. The
public modulus is a multiple of half the private key (Sb, Sbr). With a
little searching we can get the common factors and recover both shadow
numbers. Here's a demonstration of all values in a keygen and ciphering,
showing borked with zero moduli.

shadow1 :  10838689
shadow2 :  121499449
base    :  1316894741382360
privkey :  900923299802569 1316894741382360
pubkey  :  56389746240577907081847078295741930609,
2283774347030095339404262922298287777443461960
adder   :  11
mbase   : 14485842155205960
borked? : mod 0
plaintext :  711
encrypted :  40093109577050891935193272668272512662999
decrypted :  711

In this example the plaintext is a factor of the ciphertext and the
private key is a factor of the public key, so it is totally insecure.
The exponentiation and addition trick doesn't work--it just shifts the
relationships of the common denominators into bigger composites. I don't
know why I didn't see that in the example in the paper, because it is
obvious to me now.

I will be checking my implementation for errors while trying to find
other ways to break it. I'll check back later and post more for anyone
else who wants to tinker, and maybe find additional breaks, or a way to
remedy them and cobble together a better toy cryptosystem to attack.

-- 
░░░█████░░░████░░░░████░░░░░ . . .    [chan] 711
░░░░░░██░░░░░██░░░░░░██░░░░░ . . .    spooky mart
░░░░░░██░░░░░██░░░░░░██░░░░░ . . .    always open
░░░░░░██░░░██████░░██████░░░ . . .    https://bitmessage.org

Back to sci.crypt | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-09-30 12:43 -0500
  Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-01 15:52 +0000
    Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-02 05:41 -0500
    Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-02 09:08 -0500
      Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-02 15:34 +0000
        Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-04 16:25 -0500
          Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-05 15:20 +0000
            Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-05 14:26 -0500
              Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-05 20:32 +0000

csiph-web