Mixing
RSA given d and d = p
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Assume we have a somehow unorthodox implementation of RSA whereby:
$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p,q$ and
$$beginalign
phi &= (p-1)(q-1)\
d &= p\
e &= d^-1bmod phi
endalign$$
I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:
$$e = fracphi j + 1p $$
Further assuming that $frac1p$ can be considered infinitesimal:
$$e ≈ jleft(qleft(1+frac1pright) -1right)$$
So basically:
$$e ≈ j(q-1)$$
Is that right? Am I missing something?
rsa modular-arithmetic
asked Sep 3 at 13:14
S. L.
485
add a comment |Â
up vote
4
down vote
favorite
Assume we have a somehow unorthodox implementation of RSA whereby:
$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p,q$ and
$$beginalign
phi &= (p-1)(q-1)\
d &= p\
e &= d^-1bmod phi
endalign$$
I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:
$$e = fracphi j + 1p $$
Further assuming that $frac1p$ can be considered infinitesimal:
$$e ≈ jleft(qleft(1+frac1pright) -1right)$$
So basically:
$$e ≈ j(q-1)$$
Is that right? Am I missing something?
rsa modular-arithmetic
asked Sep 3 at 13:14
S. L.
485
1
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Assume we have a somehow unorthodox implementation of RSA whereby:
$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p,q$ and
$$beginalign
phi &= (p-1)(q-1)\
d &= p\
e &= d^-1bmod phi
endalign$$
I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:
$$e = fracphi j + 1p $$
Further assuming that $frac1p$ can be considered infinitesimal:
$$e ≈ jleft(qleft(1+frac1pright) -1right)$$
So basically:
$$e ≈ j(q-1)$$
Is that right? Am I missing something?
rsa modular-arithmetic
asked Sep 3 at 13:14
S. L.
485
Assume we have a somehow unorthodox implementation of RSA whereby:
$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p,q$ and
$$beginalign
phi &= (p-1)(q-1)\
d &= p\
e &= d^-1bmod phi
endalign$$
I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:
$$e = fracphi j + 1p $$
Further assuming that $frac1p$ can be considered infinitesimal:
$$e ≈ jleft(qleft(1+frac1pright) -1right)$$
So basically:
$$e ≈ j(q-1)$$
Is that right? Am I missing something?
rsa modular-arithmetic
asked Sep 3 at 13:14
S. L.
485
edited Sep 3 at 16:33
asked Sep 3 at 13:14
S. L.
485
asked Sep 3 at 13:14
S. L.
485
asked Sep 3 at 13:14
S. L.
485
485
1
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28
add a comment |Â
1
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28
1
1
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
8
down vote
accepted
Yes, it's broken. Here is the approach I see:
$$p = textgcd( n, r^e - r bmod n)$$
with quite high probability, for random $r$.
This happens because $e equiv 1 bmod p-1$, and hence $r^e equiv r pmod p$ (for any $r$). It is unlikely that $r^e equiv r pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.
answered Sep 3 at 16:46
poncho
85.5k2127216
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
accepted
Yes, it's broken. Here is the approach I see:
$$p = textgcd( n, r^e - r bmod n)$$
with quite high probability, for random $r$.
This happens because $e equiv 1 bmod p-1$, and hence $r^e equiv r pmod p$ (for any $r$). It is unlikely that $r^e equiv r pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.
answered Sep 3 at 16:46
poncho
85.5k2127216
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
 |Â
show 1 more comment
up vote
8
down vote
accepted
Yes, it's broken. Here is the approach I see:
$$p = textgcd( n, r^e - r bmod n)$$
with quite high probability, for random $r$.
This happens because $e equiv 1 bmod p-1$, and hence $r^e equiv r pmod p$ (for any $r$). It is unlikely that $r^e equiv r pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.
answered Sep 3 at 16:46
poncho
85.5k2127216
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
 |Â
show 1 more comment
up vote
8
down vote
accepted
up vote
8
down vote
accepted
Yes, it's broken. Here is the approach I see:
$$p = textgcd( n, r^e - r bmod n)$$
with quite high probability, for random $r$.
This happens because $e equiv 1 bmod p-1$, and hence $r^e equiv r pmod p$ (for any $r$). It is unlikely that $r^e equiv r pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.
answered Sep 3 at 16:46
poncho
85.5k2127216
Yes, it's broken. Here is the approach I see:
$$p = textgcd( n, r^e - r bmod n)$$
with quite high probability, for random $r$.
This happens because $e equiv 1 bmod p-1$, and hence $r^e equiv r pmod p$ (for any $r$). It is unlikely that $r^e equiv r pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.
answered Sep 3 at 16:46
poncho
85.5k2127216
edited Sep 3 at 20:52
answered Sep 3 at 16:46
poncho
85.5k2127216
answered Sep 3 at 16:46
poncho
85.5k2127216
answered Sep 3 at 16:46
poncho
85.5k2127216
85.5k2127216
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
 |Â
show 1 more comment
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
Awesome, exactly what I was looking for! Thanks!
– S. L.
Sep 4 at 6:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem?
– S. L.
Sep 4 at 15:59
1
1
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
@S.L. Two things: $d = p$ implies $d equiv 1 pmodp-1$, which imples that $d^-1 = e equiv 1 pmodp-1$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p equiv a pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^k(p-1) + 1 equiv a pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result.
– poncho
Sep 4 at 16:12
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^k(p-1)+1 = a (mod (k(p-1)+1)$$ ? Thanks!
– S. L.
Sep 4 at 16:37
1
1
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
@S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^k(p-1)+1 equiv a pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$)
– poncho
Sep 4 at 16:47
 |Â
show 1 more comment
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62008%2frsa-given-d-and-d-p%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Do you mean $e = mathrmmodinv(d,phi)?$ Otherwise explain how to get $e.$
– gammatester
Sep 3 at 15:28