Tjyylli

How to type dʒ symbol (IPA) on Mac?

Can I make popcorn with any corn?

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

Set-theoretical foundations of Mathematics with only bounded quantifiers

"which" command doesn't work / path of Safari?

If Manufacturer spice model and Datasheet give different values which should I use?

Japan - Plan around max visa duration

Are tax years 2016 & 2017 back taxes deductible for tax year 2018?

Why are only specific transaction types accepted into the mempool?

Why Is Death Allowed In the Matrix?

Why is the design of haulage companies so “special”?

Why is an old chain unsafe?

I probably found a bug with the sudo apt install function

What would the Romans have called "sorcery"?

Can an x86 CPU running in real mode be considered to be basically an 8086 CPU?

Continuity at a point in terms of closure

Why can't I see bouncing of a switch on an oscilloscope?

A Journey Through Space and Time

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?

How do I create uniquely male characters?

How long does it take to type this?

Can I interfere when another PC is about to be attacked?

RSA: Danger of using p to create q

Reducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature using only RSA encryptionFinding Private Key $d$ using RSAInverting RSA using an oracleRSA encryption using multiplicationRSA encryption using euclidean alorithmBreaking RSA using Chinese Remainder TheoremManually encrypt using RSA X509 in .NETGenerate shared secrets using RSABreaking RSA using known root

3

$begingroup$

Assume my prime generation is as follows:

1. Pick a number $p$ between 1000 and 9999. $p=abcd$.




2. Make sure $p$ is prime




3. Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$




4. Make sure $q$ is prime.

Is the resulting $n = p·q$ more easily factorable?

My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?

rsa

share|improve this question

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
  $endgroup$
  – Ilmari Karonen
  yesterday
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
  $endgroup$
  – Ilmari Karonen
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
  $endgroup$
  – enedil
  yesterday
  

  
  
  
  

add a comment | 

3

$begingroup$

Assume my prime generation is as follows:

1. Pick a number $p$ between 1000 and 9999. $p=abcd$.




2. Make sure $p$ is prime




3. Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$




4. Make sure $q$ is prime.

Is the resulting $n = p·q$ more easily factorable?

My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?

rsa

share|improve this question

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Of course, any product of two 4-digit primes is trivially factorable by trial division anyway, since there are only 1061 primes between 1000 and 9999. Add in the digit reversal requirement, and there are only 76(!) possible pairs to consider.
  $endgroup$
  – Ilmari Karonen
  yesterday
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Nat: My fault, I added the "$= pq$" for context in an edit, and didn't notice the potential ambiguity. I see Paŭlo has already fixed it.
  $endgroup$
  – Ilmari Karonen
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'd just like to add that this is inspired by a contest that just ended (12 minutes ago).
  $endgroup$
  – enedil
  yesterday
  

  
  
  
  

add a comment | 

$begingroup$

Assume my prime generation is as follows:

1. Pick a number $p$ between 1000 and 9999. $p=abcd$.




2. Make sure $p$ is prime




3. Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$




4. Make sure $q$ is prime.

Is the resulting $n = p·q$ more easily factorable?

My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?

rsa

share|improve this question

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

$endgroup$

share|improve this question

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

share|improve this question

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

edited yesterday

Paŭlo Ebermann

18.9k560106

edited yesterday

Paŭlo Ebermann

18.9k560106

asked 2 days ago

S. L.S. L.

957

asked 2 days ago

S. L.S. L.

957

2 Answers
2

active

oldest

votes

9

$begingroup$

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since ${x,y} le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in {0, 1}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in {W_0, W_1}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.

share|improve this answer

edited 2 days ago

answered 2 days ago

GillesGilles

8,41232756

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
  $endgroup$
  – S. L.
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @S.L. Woops, different equation, but same principle.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  

add a comment | 

3

$begingroup$

Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):

We have $n = xyB^2 + (x^2+y^2)B + xy$

First, compute $n bmod B$, that gives you $xy bmod B$

Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$

Pasting those two together will give you a total of three possibilities of $xy$.

Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.

(Thanks for Giles for pointing out this last part)

share|improve this answer

edited 2 days ago

answered 2 days ago

ponchoponcho

93.9k2146245

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gilles: yup, you're right; I'll update the answer
  $endgroup$
  – poncho
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
  $endgroup$
  – S. L.
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
  $endgroup$
  – poncho
  2 days ago
  
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcrypto.stackexchange.com%2fquestions%2f68562%2frsa-danger-of-using-p-to-create-q%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

9

$begingroup$

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since ${x,y} le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in {0, 1}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in {W_0, W_1}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.

share|improve this answer

edited 2 days ago

answered 2 days ago

GillesGilles

8,41232756

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
  $endgroup$
  – S. L.
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @S.L. Woops, different equation, but same principle.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  

add a comment | 

9

$begingroup$

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since ${x,y} le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in {0, 1}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in {W_0, W_1}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.

share|improve this answer

edited 2 days ago

answered 2 days ago

GillesGilles

8,41232756

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
  $endgroup$
  – S. L.
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @S.L. Woops, different equation, but same principle.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  

add a comment | 

$begingroup$

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since ${x,y} le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in {0, 1}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in {W_0, W_1}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.

share|improve this answer

edited 2 days ago

answered 2 days ago

GillesGilles

8,41232756

$endgroup$

share|improve this answer

edited 2 days ago

answered 2 days ago

GillesGilles

8,41232756

answered 2 days ago

GillesGilles

8,41232756

answered 2 days ago

GillesGilles

8,41232756

3

$begingroup$

Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):

We have $n = xyB^2 + (x^2+y^2)B + xy$

First, compute $n bmod B$, that gives you $xy bmod B$

Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$

Pasting those two together will give you a total of three possibilities of $xy$.

Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.

(Thanks for Giles for pointing out this last part)

share|improve this answer

edited 2 days ago

answered 2 days ago

ponchoponcho

93.9k2146245

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gilles: yup, you're right; I'll update the answer
  $endgroup$
  – poncho
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
  $endgroup$
  – S. L.
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
  $endgroup$
  – poncho
  2 days ago
  
  
  

  
  
  
  

add a comment | 

3

$begingroup$

Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):

We have $n = xyB^2 + (x^2+y^2)B + xy$

First, compute $n bmod B$, that gives you $xy bmod B$

Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$

Pasting those two together will give you a total of three possibilities of $xy$.

Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.

(Thanks for Giles for pointing out this last part)

share|improve this answer

edited 2 days ago

answered 2 days ago

ponchoponcho

93.9k2146245

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
  $endgroup$
  – Gilles
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Gilles: yup, you're right; I'll update the answer
  $endgroup$
  – poncho
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
  $endgroup$
  – S. L.
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $(n - B^2(xy bmod B)) / B^3 = lfloor(xy/B) rfloor + x^2 / B^2 + y^2 / B^2 + xy / B^3$; we know that $x^2 / B^2, y^2 / B^2, xy / B^3$ are all less than 1 (and $ge 0$), and so the sum must be in the interval $[0, 3)$, that is, two or less once you round down...
  $endgroup$
  – poncho
  2 days ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):

We have $n = xyB^2 + (x^2+y^2)B + xy$

First, compute $n bmod B$, that gives you $xy bmod B$

Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$

Pasting those two together will give you a total of three possibilities of $xy$.

Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.

(Thanks for Giles for pointing out this last part)

share|improve this answer

edited 2 days ago

answered 2 days ago

ponchoponcho

93.9k2146245

$endgroup$

share|improve this answer

edited 2 days ago

answered 2 days ago

ponchoponcho

93.9k2146245

answered 2 days ago

ponchoponcho

93.9k2146245

answered 2 days ago

ponchoponcho

93.9k2146245