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

SugarBug <3883@sugar.bug> writes:
> 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?

Just post your tutor's email address, and we can send the answers
directly to him, that'll save you all effort.

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have
gained some understanding of the world in which we live. As such, we can cast
aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/