RSA: Danger of using p to create qReducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature...

Arrow those variables!

Why is 150k or 200k jobs considered good when there's 300k+ births a month?

What are these boxed doors outside store fronts in New York?

Is it legal for company to use my work email to pretend I still work there?

Can I ask the recruiters in my resume to put the reason why I am rejected?

Roll the carpet

Can a Cauchy sequence converge for one metric while not converging for another?

Codimension of non-flat locus

Today is the Center

RSA: Danger of using p to create q

Approximately how much travel time was saved by the opening of the Suez Canal in 1869?

Theorems that impeded progress

meaning of に in 本当に?

Are the number of citations and number of published articles the most important criteria for a tenure promotion?

infared filters v nd

What typically incentivizes a professor to change jobs to a lower ranking university?

Why is Minecraft giving an OpenGL error?

tikz convert color string to hex value

Intersection point of 2 lines defined by 2 points each

Why are electrically insulating heatsinks so rare? Is it just cost?

How does one intimidate enemies without having the capacity for violence?

Languages that we cannot (dis)prove to be Context-Free

I'm flying to France today and my passport expires in less than 2 months

Add text to same line using sed



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 = pq$ 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?










share|improve this question











$endgroup$








  • 4




    $begingroup$
    I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
    $endgroup$
    – Ella Rose
    9 hours ago










  • $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
    1 hour ago
















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 = pq$ 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?










share|improve this question











$endgroup$








  • 4




    $begingroup$
    I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
    $endgroup$
    – Ella Rose
    9 hours ago










  • $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
    1 hour ago














3












3








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 = pq$ 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?










share|improve this question











$endgroup$




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 = pq$ 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















share|improve this question













share|improve this question




share|improve this question








edited 2 hours ago









Ilmari Karonen

35.7k373138




35.7k373138










asked 10 hours ago









S. L.S. L.

957




957








  • 4




    $begingroup$
    I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
    $endgroup$
    – Ella Rose
    9 hours ago










  • $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
    1 hour ago














  • 4




    $begingroup$
    I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
    $endgroup$
    – Ella Rose
    9 hours ago










  • $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
    1 hour ago








4




4




$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose
9 hours ago




$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose
9 hours ago












$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
1 hour ago




$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
1 hour ago










2 Answers
2






active

oldest

votes


















6












$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











$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.
    8 hours ago










  • $begingroup$
    @S.L. Woops, different equation, but same principle.
    $endgroup$
    – Gilles
    6 hours ago



















2












$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











$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
    6 hours ago










  • $begingroup$
    @Gilles: yup, you're right; I'll update the answer
    $endgroup$
    – poncho
    6 hours 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.
    6 hours ago












  • $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
    5 hours ago














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


















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















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









6












$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











$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.
    8 hours ago










  • $begingroup$
    @S.L. Woops, different equation, but same principle.
    $endgroup$
    – Gilles
    6 hours ago
















6












$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











$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.
    8 hours ago










  • $begingroup$
    @S.L. Woops, different equation, but same principle.
    $endgroup$
    – Gilles
    6 hours ago














6












6








6





$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











$endgroup$



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














share|improve this answer



share|improve this answer








edited 6 hours ago

























answered 10 hours ago









GillesGilles

8,37232756




8,37232756












  • $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.
    8 hours ago










  • $begingroup$
    @S.L. Woops, different equation, but same principle.
    $endgroup$
    – Gilles
    6 hours ago


















  • $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.
    8 hours ago










  • $begingroup$
    @S.L. Woops, different equation, but same principle.
    $endgroup$
    – Gilles
    6 hours ago
















$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.
8 hours ago




$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.
8 hours ago












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




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











2












$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











$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
    6 hours ago










  • $begingroup$
    @Gilles: yup, you're right; I'll update the answer
    $endgroup$
    – poncho
    6 hours 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.
    6 hours ago












  • $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
    5 hours ago


















2












$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











$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
    6 hours ago










  • $begingroup$
    @Gilles: yup, you're right; I'll update the answer
    $endgroup$
    – poncho
    6 hours 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.
    6 hours ago












  • $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
    5 hours ago
















2












2








2





$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











$endgroup$



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














share|improve this answer



share|improve this answer








edited 6 hours ago

























answered 7 hours ago









ponchoponcho

93.8k2146244




93.8k2146244












  • $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
    6 hours ago










  • $begingroup$
    @Gilles: yup, you're right; I'll update the answer
    $endgroup$
    – poncho
    6 hours 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.
    6 hours ago












  • $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
    5 hours ago




















  • $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
    6 hours ago










  • $begingroup$
    @Gilles: yup, you're right; I'll update the answer
    $endgroup$
    – poncho
    6 hours 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.
    6 hours ago












  • $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
    5 hours ago


















$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
6 hours ago




$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
6 hours ago












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




$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
6 hours 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.
6 hours 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.
6 hours ago














$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
5 hours ago






$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
5 hours ago




















draft saved

draft discarded




















































Thanks for contributing an answer to Cryptography Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














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















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

El tren de la libertad Índice Antecedentes "Porque yo decido" Desarrollo de la...

Castillo d'Acher Características Menú de navegación

Puerta de Hutt Referencias Enlaces externos Menú de navegación15°58′00″S 5°42′00″O /...