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

Groups > sci.crypt > #50407

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

Show all headers | View raw

On 10/5/21 10:20 AM, Peter Pearson wrote:

>> pubkey (Sara, Bra)  :
>>    57333613759833334679914302455108124,
>>    320632539812891314264995223041035707802067
>>
>> ciphertext (e) :
>>    289609149406663016296773405950344946146989
> 
> So, the challenge is to find the secret message m such that
> e = (m * Sara) mod Bra.
> 
>     $ python
>     >>> import numbertheory
>     >>> Sara = 57333613759833334679914302455108124
>     >>> Bra = 320632539812891314264995223041035707802067
>     >>> e = 289609149406663016296773405950344946146989
>     >>> d = numbertheory.inverse_mod(Sara, Bra)
>     Traceback (most recent call last):
>       File "<stdin>", line 1, in <module>
>       File "numbertheory.py", line 226, in inverse_mod
>         assert d == 1
>     AssertionError
> 
> Oops!  Stubbed my toe.
> 
> Note that if Sara and Bra have a greatest common divisor greater than 1,
> then there will be more than one plaintext in the range [0, Bra-1]
> that encrypt to the same ciphertext.  For that reason, I assumed that
> Sara and Bra were relatively prime.  But Sara and Bra having a common
> factor is more of a problem for the users of the cipher than for the
> attacker.  The attack continues:
> 
>     >>> g = numbertheory.gcd(Sara, Bra)
>     >>> g
>     3L
>     >>> d = numbertheory.inverse_mod(Sara/g, Bra/g)
>     >>> m = ((e/g)*d) % (Bra/g)
>     >>> m
>     33013301L
>     >>> (Sara * m) % Bra
>     289609149406663016296773405950344946146989L
>     >>> (Sara * m) % Bra - e
>     0L
> 
> So, m encrypts to the challenge's ciphertext.
> 
> And here are two more m's that encrypt to the same ciphertext:
> 
>     >>> m1 = m + Bra/g
>     >>> (Sara * m1) % Bra
>     289609149406663016296773405950344946146989L
>     >>> m2 = m1 + Bra/g
>     >>> (Sara * m2) % Bra
>     289609149406663016296773405950344946146989L

'3301330' is the correct m. This replicates repeatedly with random inputs.

Although the exponentiation does seem to make computing inverse or
logarithm to the seed (Sa, Sb) values harder, it doesn't hide common
factors, and worse the plaintext becomes a divisor of the ciphertext. We
can guess the plaintext by randomly sampling and re-arranging the
ciphertext factors until we get one that works as a key to whatever
stream cipher would be packaged with the payload. Even with big keys a
GPU sort would crunch right through.

Since both the public key numbers are raised to the same power, subject
to the same modulus divisor, then incremented with the same additive,
they still share factors with the hidden key material and the plaintext.

Thanks for cracking at this. Do you notice any more ways to break this
system?

-- 
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███        [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███        spooky mart
██████░░██░░███░░██░░█████░░██░░███        always open
██████░░██░░███░░██░░█████░░██░░███        stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█        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