Mixing
![Group of units of $mathbb F_p[x]/(x^3-1)$](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Is security of the modulus needed to maintain the “discrete logarithm problem�
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
After a serious google search, I have been unable to find a definite yes/no answer to the following question.
Assume I have c, e and m, and I compute $r = c ^ e mod m$
This is with regard to the discrete-logarithm problem. My understanding is that revealing r and c does not compromise e, but what about revealing m?
I know enough about cryptography to know that I should never assume anything, thus my reason for asking.
modular-arithmetic discrete-logarithms
asked Jul 28 at 21:55
dgnuff
1434
add a comment |Â
up vote
0
down vote
favorite
After a serious google search, I have been unable to find a definite yes/no answer to the following question.
Assume I have c, e and m, and I compute $r = c ^ e mod m$
This is with regard to the discrete-logarithm problem. My understanding is that revealing r and c does not compromise e, but what about revealing m?
I know enough about cryptography to know that I should never assume anything, thus my reason for asking.
modular-arithmetic discrete-logarithms
asked Jul 28 at 21:55
dgnuff
1434
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
After a serious google search, I have been unable to find a definite yes/no answer to the following question.
Assume I have c, e and m, and I compute $r = c ^ e mod m$
This is with regard to the discrete-logarithm problem. My understanding is that revealing r and c does not compromise e, but what about revealing m?
I know enough about cryptography to know that I should never assume anything, thus my reason for asking.
modular-arithmetic discrete-logarithms
asked Jul 28 at 21:55
dgnuff
1434
After a serious google search, I have been unable to find a definite yes/no answer to the following question.
Assume I have c, e and m, and I compute $r = c ^ e mod m$
This is with regard to the discrete-logarithm problem. My understanding is that revealing r and c does not compromise e, but what about revealing m?
I know enough about cryptography to know that I should never assume anything, thus my reason for asking.
modular-arithmetic discrete-logarithms
asked Jul 28 at 21:55
dgnuff
1434
edited Jul 29 at 2:09
asked Jul 28 at 21:55
dgnuff
1434
asked Jul 28 at 21:55
dgnuff
1434
asked Jul 28 at 21:55
dgnuff
1434
1434
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48
add a comment |Â
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
It looks like you are talking about public-key cryptography. For RSA, $e$ and $m$ are the public keys for the recipient; $c$ is the message to be encrypted and presumably is private to the sender, while $r$ is the encrypted message that is presumed to be open to interception. The secret decrypt value is $d:= e^-1 bmod$ $lambda(m)$, which is hard to discover since $m$ is a number that is chosen to be hard to factorize - the product of two large primes.
Even knowing all of $r$ and $c$ for a set of messages (and given that $e$ and $m$ are public anyway), the decrypt key value of $d$ is still secure by the size of the numbers involved.
One of the interesting tricks is to send a message encrypted with your own key but using the decrypt exponent $d$ instead of the public encrpyt $e$. Then anyone can decrypt it but it can only have come from you. Then wrapping this message (suitably tagged) in someone else's public key means only they can read it, and they know that only you could have sent it.
answered Jul 28 at 23:15
Joffan
31.8k43169
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
It looks like you are talking about public-key cryptography. For RSA, $e$ and $m$ are the public keys for the recipient; $c$ is the message to be encrypted and presumably is private to the sender, while $r$ is the encrypted message that is presumed to be open to interception. The secret decrypt value is $d:= e^-1 bmod$ $lambda(m)$, which is hard to discover since $m$ is a number that is chosen to be hard to factorize - the product of two large primes.
Even knowing all of $r$ and $c$ for a set of messages (and given that $e$ and $m$ are public anyway), the decrypt key value of $d$ is still secure by the size of the numbers involved.
One of the interesting tricks is to send a message encrypted with your own key but using the decrypt exponent $d$ instead of the public encrpyt $e$. Then anyone can decrypt it but it can only have come from you. Then wrapping this message (suitably tagged) in someone else's public key means only they can read it, and they know that only you could have sent it.
answered Jul 28 at 23:15
Joffan
31.8k43169
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
add a comment |Â
up vote
0
down vote
It looks like you are talking about public-key cryptography. For RSA, $e$ and $m$ are the public keys for the recipient; $c$ is the message to be encrypted and presumably is private to the sender, while $r$ is the encrypted message that is presumed to be open to interception. The secret decrypt value is $d:= e^-1 bmod$ $lambda(m)$, which is hard to discover since $m$ is a number that is chosen to be hard to factorize - the product of two large primes.
Even knowing all of $r$ and $c$ for a set of messages (and given that $e$ and $m$ are public anyway), the decrypt key value of $d$ is still secure by the size of the numbers involved.
One of the interesting tricks is to send a message encrypted with your own key but using the decrypt exponent $d$ instead of the public encrpyt $e$. Then anyone can decrypt it but it can only have come from you. Then wrapping this message (suitably tagged) in someone else's public key means only they can read it, and they know that only you could have sent it.
answered Jul 28 at 23:15
Joffan
31.8k43169
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
add a comment |Â
up vote
0
down vote
up vote
0
down vote
It looks like you are talking about public-key cryptography. For RSA, $e$ and $m$ are the public keys for the recipient; $c$ is the message to be encrypted and presumably is private to the sender, while $r$ is the encrypted message that is presumed to be open to interception. The secret decrypt value is $d:= e^-1 bmod$ $lambda(m)$, which is hard to discover since $m$ is a number that is chosen to be hard to factorize - the product of two large primes.
Even knowing all of $r$ and $c$ for a set of messages (and given that $e$ and $m$ are public anyway), the decrypt key value of $d$ is still secure by the size of the numbers involved.
One of the interesting tricks is to send a message encrypted with your own key but using the decrypt exponent $d$ instead of the public encrpyt $e$. Then anyone can decrypt it but it can only have come from you. Then wrapping this message (suitably tagged) in someone else's public key means only they can read it, and they know that only you could have sent it.
answered Jul 28 at 23:15
Joffan
31.8k43169
It looks like you are talking about public-key cryptography. For RSA, $e$ and $m$ are the public keys for the recipient; $c$ is the message to be encrypted and presumably is private to the sender, while $r$ is the encrypted message that is presumed to be open to interception. The secret decrypt value is $d:= e^-1 bmod$ $lambda(m)$, which is hard to discover since $m$ is a number that is chosen to be hard to factorize - the product of two large primes.
Even knowing all of $r$ and $c$ for a set of messages (and given that $e$ and $m$ are public anyway), the decrypt key value of $d$ is still secure by the size of the numbers involved.
One of the interesting tricks is to send a message encrypted with your own key but using the decrypt exponent $d$ instead of the public encrpyt $e$. Then anyone can decrypt it but it can only have come from you. Then wrapping this message (suitably tagged) in someone else's public key means only they can read it, and they know that only you could have sent it.
answered Jul 28 at 23:15
Joffan
31.8k43169
edited Jul 29 at 0:53
answered Jul 28 at 23:15
Joffan
31.8k43169
answered Jul 28 at 23:15
Joffan
31.8k43169
answered Jul 28 at 23:15
Joffan
31.8k43169
31.8k43169
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
add a comment |Â
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
If the talk is really on the discrete logarithm problem, then the "secret message" is $e$, not $c$ (and $m$ is usually taken to be prime).
– metamorphy
Jul 29 at 0:22
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
@metamorphy No, the whole point of $m$ is that it is not prime.
– Joffan
Jul 29 at 0:33
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
It is the point for RSA. For DLP, the security concerns on $m$ are "completely different".
– metamorphy
Jul 29 at 0:45
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
@metamorphy OK added that I am specifically talking about RSA. If you want to add an answer about DLP I will read with interest.
– Joffan
Jul 29 at 0:54
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
Joffan is correct, this is for the discrete logarithm problem, and as noted in Randall's comment to my original post, r, c, and m can all be published without compromising e, and m will be prime. I'll edit the question to clarify that. -- Edit -- I will add that I did include the Discrete-Logarithm Tag when originally posting.
– dgnuff
Jul 29 at 2:09
add a 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%2fmath.stackexchange.com%2fquestions%2f2865602%2fis-security-of-the-modulus-needed-to-maintain-the-discrete-logarithm-problem%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
Everyone must know the modulus, otherwise how are they supposed to do the calculations? You want to conceal its factors.
– Randall
Jul 28 at 21:57
@Randall Thanks - post that as an answer, and I'll accept it.
– dgnuff
Jul 28 at 21:59
Thanks, I’ll let someone else take it. I’m on my phone ;)
– Randall
Jul 28 at 22:02
Although "discreet" is also somewhat genre-appropriate, in this case it's the "discrete" logarithm problem.
– SolveIt
Jul 29 at 1:48