Fdtxjr

What was the first language to use conditional keywords?

How do I find out the mythology and history of my Fortress?

How fail-safe is nr as stop bytes?

Is grep documentation about ignoring case wrong, since it doesn't ignore case in filenames?

Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?

Can anything be seen from the center of the Boötes void? How dark would it be?

Exposing GRASS GIS add-on in QGIS Processing framework?

What does it mean that physics no longer uses mechanical models to describe phenomena?

"Lost his faith in humanity in the trenches of Verdun" — last line of an SF story

Parallel Computing Problem

What does Turing mean by this statement?

Using audio cues to encourage good posture

Converted a Scalar function to a TVF function for parallel execution-Still running in Serial mode

Can a new player join a group only when a new campaign starts?

Importance of からだ in this sentence

What is "gratricide"?

How to improve on this Stylesheet Manipulation for Message Styling

Is there any word for a place full of confusion?

Time to Settle Down!

What is the difference between globalisation and imperialism?

How to play a character with a disability or mental disorder without being offensive?

Triggering an ultrasonic sensor

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

Crossing US/Canada Border for less than 24 hours

Common modulus attack question RSA.

0

$begingroup$

If we are in the context of understanding how Common Modulus Attack for RSA:

$C_1=M^e_1 pmodn $

$C_2=M^e_2 pmod n $

We know that if $gcd(e_1,e_2)=1$ the attack works fine.

¿What would happen if $gcd(e_1,e_2)>1$?

cryptography

share|cite|improve this question

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

$endgroup$

add a comment | 

0

$begingroup$

If we are in the context of understanding how Common Modulus Attack for RSA:

$C_1=M^e_1 pmodn $

$C_2=M^e_2 pmod n $

We know that if $gcd(e_1,e_2)=1$ the attack works fine.

¿What would happen if $gcd(e_1,e_2)>1$?

cryptography

share|cite|improve this question

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

$endgroup$

add a comment | 

$begingroup$

If we are in the context of understanding how Common Modulus Attack for RSA:

$C_1=M^e_1 pmodn $

$C_2=M^e_2 pmod n $

We know that if $gcd(e_1,e_2)=1$ the attack works fine.

¿What would happen if $gcd(e_1,e_2)>1$?

cryptography

share|cite|improve this question

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

$endgroup$

share|cite|improve this question

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

share|cite|improve this question

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

edited Mar 29 at 22:27

Henno Brandsma

117k350128

edited Mar 29 at 22:27

Henno Brandsma

117k350128

asked Mar 27 at 19:35

LecterLecter

11311

asked Mar 27 at 19:35

LecterLecter

11311

1 Answer
1

active

oldest

votes

1

$begingroup$

You would need to be able to extract $k$th roots where $k=gcd(e_1,e_2)$ (and to do so efficiently). The common modulus attack allows one to recover $m^k bmod n$ where $m$ is the desired plaintext. However, extracting $k$th roots is probably hard. (Extracting $e$th roots would lead to an immediate breaking of RSA through a single known ciphertext message: knowledge of $c$ and that $c=m^e$ would give us $m$ immediately by taking the $e$th root.)

share|cite|improve this answer

edited Mar 28 at 0:23

answered Mar 27 at 19:39

RandallRandall

10.8k11431

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3165012%2fcommon-modulus-attack-question-rsa%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

You would need to be able to extract $k$th roots where $k=gcd(e_1,e_2)$ (and to do so efficiently). The common modulus attack allows one to recover $m^k bmod n$ where $m$ is the desired plaintext. However, extracting $k$th roots is probably hard. (Extracting $e$th roots would lead to an immediate breaking of RSA through a single known ciphertext message: knowledge of $c$ and that $c=m^e$ would give us $m$ immediately by taking the $e$th root.)

share|cite|improve this answer

edited Mar 28 at 0:23

answered Mar 27 at 19:39

RandallRandall

10.8k11431

$endgroup$

add a comment | 

1

$begingroup$

You would need to be able to extract $k$th roots where $k=gcd(e_1,e_2)$ (and to do so efficiently). The common modulus attack allows one to recover $m^k bmod n$ where $m$ is the desired plaintext. However, extracting $k$th roots is probably hard. (Extracting $e$th roots would lead to an immediate breaking of RSA through a single known ciphertext message: knowledge of $c$ and that $c=m^e$ would give us $m$ immediately by taking the $e$th root.)

share|cite|improve this answer

edited Mar 28 at 0:23

answered Mar 27 at 19:39

RandallRandall

10.8k11431

$endgroup$

add a comment | 

$begingroup$

You would need to be able to extract $k$th roots where $k=gcd(e_1,e_2)$ (and to do so efficiently). The common modulus attack allows one to recover $m^k bmod n$ where $m$ is the desired plaintext. However, extracting $k$th roots is probably hard. (Extracting $e$th roots would lead to an immediate breaking of RSA through a single known ciphertext message: knowledge of $c$ and that $c=m^e$ would give us $m$ immediately by taking the $e$th root.)

share|cite|improve this answer

edited Mar 28 at 0:23

answered Mar 27 at 19:39

RandallRandall

10.8k11431

$endgroup$

share|cite|improve this answer

edited Mar 28 at 0:23

answered Mar 27 at 19:39

RandallRandall

10.8k11431

answered Mar 27 at 19:39

RandallRandall

10.8k11431

answered Mar 27 at 19:39

RandallRandall

10.8k11431