Path: ...!news.misty.com!weretis.net!feeder6.news.weretis.net!news.quux.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: SugarBug <3883@sugar.bug>
Newsgroups: sci.crypt
Subject: Exploration of Diffie-Hellman Multiplication versus Exponentiation
Date: Mon, 15 Apr 2024 14:59:20 -0500
Organization: Baggy Jeans Mafia (sybershock.com)
Message-ID: <2d79d2a2ad4bb66ed7e75c60f482a03d$1@sybershock.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: i2pn2.org;
	logging-data="1289059"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="yZybWhCr+jI4C3MuGpPde+DhCwsjQrVZrsCOigcx7fM";
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 3163
Lines: 79

Notation
--------

        [^] = power or exponentiation, NOT exclusive or.
        [*] = multiplication.

Exploration
-----------

With simple Diffie-Hellman Key Exchange we sometimes see something like this:

(x ^ y) mod M where x, M are primes and x, y are less than M

or x, y, M are primes and x, y are less than M

with attacker knowing x, M and solving to recover y.

Example 1
---------

(3301 ^ 1033) mod 9901 = 5711

with attacker knowing x, M and solving to recover y.

we can do similarly with large integers using singular multiplication instead of exponentiation:

Example 2
---------

x, y are secret and M is public,

and such that (x * y) mod M is used instead of (x ^ y) mod M:

7614733470835803029 * 7614733470835803029 mod 17387392922984910589
= 5287290486333094173

with attacker knowing M and solving to recover x, y.

Of course the integers must be considerably larger for difficulty.

Besides the number of multiplications required for exponentiation with large exponents, what other property of exponentiation makes it the go-to choice over simple multiplication with Diffie-Hellman Key Exchange problems?

Or asked another way, given the modulus remainder:

Example 3
---------

public modulus: 666019804555242738147912491645368766591
modulus remainder: 307023976544267555158714704165625061584

such that (x * y) mod M is used instead of (x ^ y) mod M:

(x * y) mod 666019804555242738147912491645368766591
= 307023976544267555158714704165625061584

with attacker knowing M and solving to recover x, y.

Question 1
----------

How difficult is it to find the two hidden prime factors, as opposed to finding the secret exponent of a known factor as in the first example?

Question 2
----------

What modern methods of attack are used to discover the hidden factors of example 3 and where can I read about them with examples?

Question 3
----------

Do any cryptosystems actually use any variation of example 3 with multiplication rather than exponentiation, and if so, which?

Question 4
----------

Per examples 1 through 3, if x, y are GREATER than modulus M, what are the implications for security or attack domain parameters and how? Or in other words, why are x and y usually chosen to be less than M, from a security perspective?

-- 
  www.sybershock.com | sci.crypt | alt.sources.crypto | alt.lite.bulb