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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 15 Apr 2024 14:59:20 -0500, LO AND BEHOLD; SugarBug
<3883@sugar.bug> determined that the following was of great importance
to SugarBug <3883@sugar.bug> and subsequently decided to freely share it
with us in <2d79d2a2ad4bb66ed7e75c60f482a03d$1@sybershock.com>:

=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Notation -------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= [^] = power or exponentiation, NOT exclusive or. [*] =
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= multiplication. =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Exploration ----------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= With simple Diffie-Hellman Key Exchange we sometimes see something like
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= this:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= (x ^ y) mod M where x, M are primes and x, y are less than M
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= or x, y, M are primes and x, y are less than M =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= with attacker knowing x, M and solving to recover y.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Example 1 --------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= (3301 ^ 1033) mod 9901 = 5711 =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= with attacker knowing x, M and solving to recover y.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= we can do similarly with large integers using singular multiplication
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= instead of exponentiation: =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Example 2 --------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= x, y are secret and M is public, =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= and such that (x * y) mod M is used instead of (x ^ y) mod M:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= 7614733470835803029 * 7614733470835803029 mod 17387392922984910589 =
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= 5287290486333094173 =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= with attacker knowing M and solving to recover x, y.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Of course the integers must be considerably larger for difficulty.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Besides the number of multiplications required for exponentiation with
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= large exponents, what other property of exponentiation makes it the
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= go-to choice over simple multiplication with Diffie-Hellman Key
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Exchange problems? =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Or asked another way, given the modulus remainder:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Example 3 --------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= public modulus: 666019804555242738147912491645368766591 modulus
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= remainder: 307023976544267555158714704165625061584
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= such that (x * y) mod M is used instead of (x ^ y) mod M:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= (x * y) mod 666019804555242738147912491645368766591 =
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= 307023976544267555158714704165625061584 =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= with attacker knowing M and solving to recover x, y.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Question 1 ---------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= How difficult is it to find the two hidden prime factors, as opposed to
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= finding the secret exponent of a known factor as in the first example?
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Question 2 ---------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= What modern methods of attack are used to discover the hidden factors of
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= example 3 and where can I read about them with examples?
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Question 3 ---------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Do any cryptosystems actually use any variation of example 3 with
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= multiplication rather than exponentiation, and if so, which?
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Question 4 ---------- =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Per examples 1 through 3, if x, y are GREATER than modulus M, what are
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= the implications for security or attack domain parameters and how? Or
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= in other words, why are x and y usually chosen to be less than M, from
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= a security perspective? =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=

Did they take away your AI account?


Most of the questions up there can be answered by a web search and research instead of begging for incorrect suggestions on usenet from mostly idiots.

--

"I'm pretty sure all gods are fictional, I'm smart enough to not proclaim I know this." - Kwills is only smart enough to doubt himself while arguing that a belief in imaginary made-up gods can't just be ignored as "mental illness" in <
mo4q0j9tcqjt68s039loiacrbarihsh9i5@4ax.com>

"If you worried half as much about your own personal life as you do everyone else's, you might almost be tolerable, obsessed stalker." -James "Checkmate" Gorman, in perhaps the most ironic and mentally-challenged statement ever made on Usenet. <MPG.
4001ba2c14cace6c98cb6f@usnews.blocknews.net>

"Trying to diminish others doesn't make you look any better. In fact, it does quite the opposite. Why are you always so bitter and angry? Do you have AIDS or something like so many other tranny girls do?" -James "Checkmate" Gorman in <MPG.
405409befd41f28898969d@test.blocknews.net>

"You should see my archive on you" -James "Checkmate" Gorman teases us with his "dosser" in <MPG.3eea81b23145043b98c338@usnews.blocknews.net>

"Sorry, nothing to see here. The joint wasn't as bad as they say, but I'm not looking to go back. I'm a model citizen, clean as a whistle. I've owned my own home for 12 years, owned my own business almost as long, don't bother anyone and they don't
bother me. You have nothing in any "police report" pertaining to me. Don't you think they would have "come a-knockin" a long time ago if they had any reason to? You're delusional and paranoid, and I have to wonder why.

Oh... I should mention that there are a LOT of trannies in prison. I don't know why, but there are. The State even has to give them hormone shots for their tiddies at taxpayer's expense, and they wear bras and panties. I found everything about them
revolting. That's why the whole "Bubba" thing is almost completely a myth, except in cell living. That shit wouldn't fly in a 100-man dorm, but trust me, those little trollops find ways to serve the willing when the lights go out. You see something, you
keep your mouth shut about it because that way you don't get in a wreck. I never partook in such activities because the whole idea is just repulsive. I think that's a big part of what I don't like about you. I've seen how they act and I've talked to a
few... total drama queens in every sense." -James "Checkmate" Gorman reminisces about prison in <MPG.3ceb37c2eddbaff98b07a@usnews.blocknews.net>

Golden Killfile, June 2005
KOTM, November 2006
Bob Allisat Memorial Hook, Line & Sinker, November 2006
Special Ops Cody Memorial Purple Heart, November 2006
Special Ops Cody Memorial Purple Heart, September 2007
Tony Sidaway Memorial "Drama Queen" Award, November 2006
Busted Urinal Award, April 2007
Order of the Holey Sockpuppet, September 2007
Barbara Woodhouse Memorial Dog Whistle, September 2006
Barbara Woodhouse Memorial Dog Whistle, April 2008
Tinfoil Sombrero, February 2007
AUK Mascot, September 2007
Putting the Awards Out of Order to Screw With the OCD Fuckheads, March 2016

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)