Main Page | Report this Page
 
   
Science Forum Index  »  Cryptography Forum  »  RSA ecnryption confusion...
Page 2 of 3    Goto page Previous  1, 2, 3  Next
Author Message
Noob...
Posted: Sun May 11, 2008 4:49 am
Guest
Peter Fairbrother wrote:

Quote:
It don't matter what you call them [...]

Word up, foo!
David Eather...
Posted: Sun May 11, 2008 3:38 pm
Guest
Peter Fairbrother wrote:
Quote:
Pubkeybreaker wrote:
On May 8, 3:01 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:
I'm trying to use RSA algorithm in .NET. My needs are somehow the
inverse of the normal usage. I want to distribute the private key (so
other can decrypt) and keep private the public key (so only me can
encrypt).

Impossible. Once someone has the private key, they can both
encrypt and decrypt. It is impossible to "keep private" the public
key

Why? Because it's "public"?

since it is trivially constructible from the private key.

Bollocks (unless the attacker knows the "public" key).

It's the same situation as a RSA signature - keep one key secret, and
let one key be known.

It don't matter what you call them, as long as they are long enough - in
fact the E and D keys are entirely interchangeable, if they are long
enough.

The terminology encryption and decryption are interchangeable, in that
it doesn't matter which key you use to encrypt - the other key will
decrypt. BUT the public key and private key are not interchangeable.
The public key gives out N which is the product of two large primes P
and Q. The security of RSA rests on the difficulty of factoring N. The
private key (even striped of all the extra info to use CRT) is much
easier to factor and can be used to reconstruct the public key. Thus
allowing large scale forgeries.


Quote:


First of all is this secure?

Yes, at least as much as RSA is.

Trivially insecure.

What I want to do is to keep E private and distribute D. Is it
possible that by having D the users can calculate E?

Yes.


No.

Not without knowing the factorisation of N (absent some other
maybe-attacks we don't know about on RSA).

If an attacker knows or can guess both keys then you are screwed -
otherwise, if he only knows one and can't guess the second, then it's
quantum computing, advances in factorisation, etc.

-- Peter Fairbrother
Pubkeybreaker...
Posted: Mon May 12, 2008 8:10 am
Guest
On May 12, 2:06 pm, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk>
wrote:
Quote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret.  This is impossible.

OK, I've just generated a new keypair. Tell me what the
so-called "public key" is please.

No problem. Just as soon as you tell me what the
private key is.

Quote:

You can't, as I'm keeping it secret.

You are keeping *everything* secret.


<plonk>
Albert...
Posted: Mon May 12, 2008 8:11 am
Guest
On May 12, 7:54 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:
Quote:
On May 12, 1:45 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:



On May 12, 6:05 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 11:46 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:

Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
On May 12, 10:01 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
If the private exponent is KNOWN, then constructing the
factors requires
a simple, polynomial time random algorithm. (hint: if the private
exponent is known,
then it is some multiple of phi(N))

Say my private exponent were 127199156618826266187587116281614661857616153.

What can you tell me about the modulus and its factors?

Am I wasting my time? It seems so.

No. I'm asking a serious question. Are you being evasive? It seems so.

I suspect you're making some assumptions about what else
is known.

Something else MUST be known.

Yes. I know this. Can you believe that's exactly why I'm
asking the question?

An exponent, *by itself* is meaningless. It is just a nonce.

Good. So you agree that your statement quoted above was false.

No. I do not agree. The statement you quoted is true.

Perhaps YOU are forgetting that regardless of whether one flips
the roles of the private and public key that for RSA, the MODULUS
is *always* known. It is a default assumption given that one is
working
with RSA.

The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret. This is impossible.

Thank you Pubkeybreaker for all the explanations. You're correct about
all the practical issues.
However based only on the mathematical definition it seems to me that
d & e are interchangeable.

All you are doing is RENAMING d & e. The public key becomes
(N, d) and the private key becomes (p,q) [or anything equivalent to
knowing p,q].

Public key is (N, e), private key is (d, > e).
if I
make public (d, N) how can someone else compute e.

This is just plain old RSA. All you have done is renamed d & e.
N and *some exponent* are public. You simply choose to call the
exponent d, instead of e. The private key now consists d^-1 mod
phi(N).
This is just *ordinary* RSA with d and e renamed. You are still
keeping the
private key private. This is not what you originally said that you
wanted to do. You
said you wanted to make the private key available to everyone, but
keep
the public key unknown.

You can call it that way...but based on the definition the public key
is the pair (N, d) and the private key is the pair (N, e). What I
asked was if it was possible to encrypt with the pair (N, d), keep
private d and decrypt using the pair (N, e). This may not be optimal,
may not be practical but based on the definition of RSA is secure.
Pubkeybreaker...
Posted: Mon May 12, 2008 8:25 am
Guest
On May 12, 2:11 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:
Quote:
On May 12, 7:54 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:





On May 12, 1:45 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 6:05 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 11:46 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:

Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
On May 12, 10:01 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
If the private exponent is KNOWN, then constructing the
factors requires
a simple, polynomial time random algorithm.   (hint: if the private
exponent is known,
then it is some multiple of phi(N))

Say my private exponent were 127199156618826266187587116281614661857616153.

What can you tell me about the modulus and its factors?

Am I wasting my time?  It seems so.

No. I'm asking a serious question. Are you being evasive? It seems so.

I suspect you're making some assumptions about what else
is known.

Something else MUST  be known.

Yes. I know this. Can you believe that's exactly why I'm
asking the question?

An exponent, *by itself* is meaningless.  It is just a nonce.

Good. So you agree that your statement quoted above was false.

No.  I do not agree. The statement you quoted is true.

Perhaps YOU are forgetting that regardless of whether one flips
the roles of the private and public key that for RSA, the MODULUS
is  *always* known.   It is a default assumption given that one is
working
with RSA.

The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret.  This is impossible.

Thank you Pubkeybreaker for all the explanations. You're correct about
all the practical issues.
However based only on the mathematical definition it seems to me that
d & e are interchangeable.

All you are doing is RENAMING d & e.   The public key becomes
(N, d) and the private key becomes (p,q)  [or anything equivalent to
knowing p,q].

Public key is (N, e), private key is (d, > e).
if I
make public (d, N) how can someone else compute e.

This is just plain old RSA.  All you have done is renamed d & e.
N  and *some exponent* are public.  You simply choose to call the
exponent d, instead of e.   The private key now consists d^-1  mod
phi(N).
This is just *ordinary* RSA  with d and e  renamed.  You are still
keeping the
private key private.  This is not what you originally said that you
wanted to do.  You
said you wanted to make the private key available to everyone, but
keep
the public key unknown.

Whubba! Whubba! Whubba! If it is kept unknown, then it IS NOT
PUBLIC!!!


Quote:

You can call it that way...but based on the definition the public key
is the pair (N, d) and the private key is the pair (N, e). What I
asked was if it was possible to encrypt with the pair (N, d), keep
private d

But you just said the PUBLIC key is (N,d). Now you want to keep
d private. You can't have it both ways!

And this enforces no secrecy at all. It isn't a cryptosystem because
now
anyone can read encrypted messages.



Quote:
and decrypt using the pair (N, e). This may not be optimal
may not be practical but based on the definition of RSA is secure


Secure? Anything that gets encrypted can be publicly decrypted!
This is the antithesis of security.
Albert...
Posted: Mon May 12, 2008 8:32 am
Guest
On May 12, 8:25 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:
Quote:
On May 12, 2:11 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:



On May 12, 7:54 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 1:45 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 6:05 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 11:46 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:

Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
On May 12, 10:01 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
If the private exponent is KNOWN, then constructing the
factors requires
a simple, polynomial time random algorithm. (hint: if the private
exponent is known,
then it is some multiple of phi(N))

Say my private exponent were 127199156618826266187587116281614661857616153.

What can you tell me about the modulus and its factors?

Am I wasting my time? It seems so.

No. I'm asking a serious question. Are you being evasive? It seems so.

I suspect you're making some assumptions about what else
is known.

Something else MUST be known.

Yes. I know this. Can you believe that's exactly why I'm
asking the question?

An exponent, *by itself* is meaningless. It is just a nonce.

Good. So you agree that your statement quoted above was false.

No. I do not agree. The statement you quoted is true.

Perhaps YOU are forgetting that regardless of whether one flips
the roles of the private and public key that for RSA, the MODULUS
is *always* known. It is a default assumption given that one is
working
with RSA.

The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret. This is impossible.

Thank you Pubkeybreaker for all the explanations. You're correct about
all the practical issues.
However based only on the mathematical definition it seems to me that
d & e are interchangeable.

All you are doing is RENAMING d & e. The public key becomes
(N, d) and the private key becomes (p,q) [or anything equivalent to
knowing p,q].

Public key is (N, e), private key is (d, > e).
if I
make public (d, N) how can someone else compute e.

This is just plain old RSA. All you have done is renamed d & e.
N and *some exponent* are public. You simply choose to call the
exponent d, instead of e. The private key now consists d^-1 mod
phi(N).
This is just *ordinary* RSA with d and e renamed. You are still
keeping the
private key private. This is not what you originally said that you
wanted to do. You
said you wanted to make the private key available to everyone, but
keep
the public key unknown.

Whubba! Whubba! Whubba! If it is kept unknown, then it IS NOT
PUBLIC!!!



You can call it that way...but based on the definition the public key
is the pair (N, d) and the private key is the pair (N, e). What I
asked was if it was possible to encrypt with the pair (N, d), keep
private d

But you just said the PUBLIC key is (N,d). Now you want to keep
d private. You can't have it both ways!

And this enforces no secrecy at all. It isn't a cryptosystem because
now
anyone can read encrypted messages.

and decrypt using the pair (N, e). This may not be optimal
may not be practical but based on the definition of RSA is secure

Secure? Anything that gets encrypted can be publicly decrypted!
This is the antithesis of security.

OK let's clarify. The definition of RSA is:
- The pair (N, d) is the public key and you encrypt using this pair.
- The pair (N, e) is the private key and you decrypt using this pair.

What I wanted to do is:
- Make private the (N, d) pair so only I can encrypt.
- Make public the (N, e) pair so anyone can decrypt.

That's all. Leaving aside everything else this seems to me possible
and secure.
Pubkeybreaker...
Posted: Mon May 12, 2008 8:48 am
Guest
On May 12, 2:32 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:
Quote:
On May 12, 8:25 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:





On May 12, 2:11 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 7:54 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 1:45 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 6:05 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 11:46 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:

Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
On May 12, 10:01 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo..co.uk
wrote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
If the private exponent is KNOWN, then constructing the
factors requires
a simple, polynomial time random algorithm.   (hint: if the private
exponent is known,
then it is some multiple of phi(N))

Say my private exponent were 127199156618826266187587116281614661857616153.

What can you tell me about the modulus and its factors?

Am I wasting my time?  It seems so.

No. I'm asking a serious question. Are you being evasive? It seems so.

I suspect you're making some assumptions about what else
is known.

Something else MUST  be known.

Yes. I know this. Can you believe that's exactly why I'm
asking the question?

An exponent, *by itself* is meaningless.  It is just a nonce.

Good. So you agree that your statement quoted above was false.

No.  I do not agree. The statement you quoted is true.

Perhaps YOU are forgetting that regardless of whether one flips
the roles of the private and public key that for RSA, the MODULUS
is  *always* known.   It is a default assumption given that one is
working
with RSA.

The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret.  This is impossible.

Thank you Pubkeybreaker for all the explanations. You're correct about
all the practical issues.
However based only on the mathematical definition it seems to me that
d & e are interchangeable.

All you are doing is RENAMING d & e.   The public key becomes
(N, d) and the private key becomes (p,q)  [or anything equivalent to
knowing p,q].

Public key is (N, e), private key is (d, > e).
if I
make public (d, N) how can someone else compute e.

This is just plain old RSA.  All you have done is renamed d & e.
N  and *some exponent* are public.  You simply choose to call the
exponent d, instead of e.   The private key now consists d^-1  mod
phi(N).
This is just *ordinary* RSA  with d and e  renamed.  You are still
keeping the
private key private.  This is not what you originally said that you
wanted to do.  You
said you wanted to make the private key available to everyone, but
keep
the public key unknown.

Whubba!  Whubba!   Whubba!   If it is kept unknown,  then it IS NOT
PUBLIC!!!

You can call it that way...but based on the definition the public key
is the pair (N, d) and the private key is the pair (N, e). What I
asked was if it was possible to encrypt with the pair (N, d), keep
private d

But you just said the PUBLIC key is (N,d). Now you want to keep
d private.  You can't have it both ways!

And  this enforces no secrecy at all.  It isn't a cryptosystem because
now
anyone can read encrypted messages.

and decrypt using the pair (N, e). This may not be optimal
may not be practical but based on the definition of RSA is secure

Secure?   Anything that gets encrypted can be publicly decrypted!
This is the antithesis of security.

OK let's clarify. The definition of RSA is:
- The pair (N, d) is the public key and you encrypt using this pair.
- The pair (N, e) is the private key and you decrypt using this pair.

What I wanted to do is:
- Make private the (N, d) pair so only I can encrypt.
- Make public the (N, e) pair so anyone can decrypt.

That's all. Leaving aside everything else this seems to me possible
and secure.-

What have you been smoking?????

If anyone can decrypt then no message is secret!!!!!!! You don't
have
a cryptosystem!!!!!!! There is no security at all!!!!!!
Risto Lankinen...
Posted: Mon May 12, 2008 10:57 am
Guest
On 12 touko, 21:48, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:
Quote:

If anyone can decrypt then no message is secret!!!!!!!   You don't
have
a cryptosystem!!!!!!!   There is no security at all!!!!!!

Perhaps it is counter-intuitive, but being able to encrypt
a message that anyone can decrypt _CAN_ be useful. Google
for 'digital signature' or 'fingerprinting' to learn more.

- Risto -
Albert...
Posted: Mon May 12, 2008 11:24 am
Guest
On May 12, 8:48 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:
Quote:
On May 12, 2:32 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:



On May 12, 8:25 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 2:11 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 7:54 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 1:45 pm, Albert <Albert.Tollk... at (no spam) gmail.com> wrote:

On May 12, 6:05 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:

On May 12, 11:46 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:

Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
On May 12, 10:01 am, Phil Carmody <thefatphil_demun... at (no spam) yahoo.co.uk
wrote:
Pubkeybreaker <pubkeybrea... at (no spam) aol.com> writes:
If the private exponent is KNOWN, then constructing the
factors requires
a simple, polynomial time random algorithm. (hint: if the private
exponent is known,
then it is some multiple of phi(N))

Say my private exponent were 127199156618826266187587116281614661857616153.

What can you tell me about the modulus and its factors?

Am I wasting my time? It seems so.

No. I'm asking a serious question. Are you being evasive? It seems so.

I suspect you're making some assumptions about what else
is known.

Something else MUST be known.

Yes. I know this. Can you believe that's exactly why I'm
asking the question?

An exponent, *by itself* is meaningless. It is just a nonce.

Good. So you agree that your statement quoted above was false.

No. I do not agree. The statement you quoted is true.

Perhaps YOU are forgetting that regardless of whether one flips
the roles of the private and public key that for RSA, the MODULUS
is *always* known. It is a default assumption given that one is
working
with RSA.

The OP clearly stated that he wanted to make the RSA private key
public
and to keep the public key secret. This is impossible.

Thank you Pubkeybreaker for all the explanations. You're correct about
all the practical issues.
However based only on the mathematical definition it seems to me that
d & e are interchangeable.

All you are doing is RENAMING d & e. The public key becomes
(N, d) and the private key becomes (p,q) [or anything equivalent to
knowing p,q].

Public key is (N, e), private key is (d, > e).
if I
make public (d, N) how can someone else compute e.

This is just plain old RSA. All you have done is renamed d & e.
N and *some exponent* are public. You simply choose to call the
exponent d, instead of e. The private key now consists d^-1 mod
phi(N).
This is just *ordinary* RSA with d and e renamed. You are still
keeping the
private key private. This is not what you originally said that you
wanted to do. You
said you wanted to make the private key available to everyone, but
keep
the public key unknown.

Whubba! Whubba! Whubba! If it is kept unknown, then it IS NOT
PUBLIC!!!

You can call it that way...but based on the definition the public key
is the pair (N, d) and the private key is the pair (N, e). What I
asked was if it was possible to encrypt with the pair (N, d), keep
private d

But you just said the PUBLIC key is (N,d). Now you want to keep
d private. You can't have it both ways!

And this enforces no secrecy at all. It isn't a cryptosystem because
now
anyone can read encrypted messages.

and decrypt using the pair (N, e). This may not be optimal
may not be practical but based on the definition of RSA is secure

Secure? Anything that gets encrypted can be publicly decrypted!
This is the antithesis of security.

OK let's clarify. The definition of RSA is:
- The pair (N, d) is the public key and you encrypt using this pair.
- The pair (N, e) is the private key and you decrypt using this pair.

What I wanted to do is:
- Make private the (N, d) pair so only I can encrypt.
- Make public the (N, e) pair so anyone can decrypt.

That's all. Leaving aside everything else this seems to me possible
and secure.-

What have you been smoking?????

If anyone can decrypt then no message is secret!!!!!!! You don't
have
a cryptosystem!!!!!!! There is no security at all!!!!!!

Depends on what you mean by secure. For my scenario is as below:
- I want to encrypt a message T.
- Send the encrypted file to anyone.
- Anyone can decrypt the file but they cannot create another encrypted
file.
Albert...
Posted: Mon May 12, 2008 11:28 am
Guest
On May 12, 10:57 pm, Risto Lankinen <rlank... at (no spam) gmail.com> wrote:
Quote:
On 12 touko, 21:48, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:



If anyone can decrypt then no message is secret!!!!!!! You don't
have
a cryptosystem!!!!!!! There is no security at all!!!!!!

Perhaps it is counter-intuitive, but being able to encrypt
a message that anyone can decrypt _CAN_ be useful. Google
for 'digital signature' or 'fingerprinting' to learn more.

- Risto -

That's true. Probably many people are wondering why I don't use
digital signatures. I will use them for practical reasons...but I
wanted to know if a solution based on RSA is valid. Basically digital
signatures are a tool based on RSA....
Phil Carmody...
Posted: Mon May 12, 2008 1:11 pm
Guest
Blind Anagram <noone at (no spam) nowhere.org> writes:
Quote:
Pubkeybreaker wrote:

The implementation is *irrelevant*. If the private key is
known, then the public key becomes *trivially* constructible.
It doesn't matter if p,q, are stored directly, if they are
stored in CRT format, or even if they are not stored at all.
If the private exponent is KNOWN, then constructing the
factors requires a simple, polynomial time random algorithm.

When d is less than N^0.29, does the reconstruction of the
factors of N from d work without knowing e?

Yes. If N, e and d are known, factoring N is trivial.
ed is a multiple of lambda(pq), can be used to
reconstruct phi(pq) = pq-p-q+1. Therefore you can
trivially find p+q. 2 equations in 2 unknowns - bingo.

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
Blind Anagram...
Posted: Mon May 12, 2008 1:16 pm
Guest
"Phil Carmody" <thefatphil_demunged at (no spam) yahoo.co.uk> wrote in message
news:87d4nrmly1.fsf at (no spam) nonospaz.fatphil.org...
Quote:
Blind Anagram <noone at (no spam) nowhere.org> writes:
Pubkeybreaker wrote:

The implementation is *irrelevant*. If the private key is
known, then the public key becomes *trivially* constructible.
It doesn't matter if p,q, are stored directly, if they are
stored in CRT format, or even if they are not stored at all.
If the private exponent is KNOWN, then constructing the
factors requires a simple, polynomial time random algorithm.

When d is less than N^0.29, does the reconstruction of the
factors of N from d work without knowing e?

Yes. If N, e and d are known, factoring N is trivial.
ed is a multiple of lambda(pq), can be used to
reconstruct phi(pq) = pq-p-q+1. Therefore you can
trivially find p+q. 2 equations in 2 unknowns - bingo.

Phil, did you miss the "without knowing e" bit?
Tim Smith...
Posted: Mon May 12, 2008 2:20 pm
Guest
In article
<cd862bab-ebab-420b-8044-03977573bb5a at (no spam) l42g2000hsc.googlegroups.com>,
Pubkeybreaker <pubkeybreaker at (no spam) aol.com> wrote:
Quote:
The implementation is *irrelevant*. If the private key is known,
then the public key becomes *trivially* constructible. It doesn't
matter if p,q, are stored directly, if they are stored in CRT
format, or even if they are not stored at all. If the private
exponent is KNOWN, then constructing the factors requires a simple,
polynomial time random algorithm. (hint: if the private exponent is
known, then it is some multiple of phi(N))

Wait a second. de = 1 mod phi(N). How can d be a multiple of phi(N)?

What the original poster was assuming was that the private key was just
(d,N), and the public key was just (e,N), and he wants to know if he can
give out (d,N) and keep (e,N) private, rather than giving out (e,N) and
keeping (d,N) private.

Given *JUST* (d,N), are you saying that there is a simple, polynomial
time algorithm to factor N?

--
--Tim Smith
Albert...
Posted: Tue May 13, 2008 3:21 am
Guest
On May 13, 1:43 pm, Thomas Pornin <por... at (no spam) bolet.org> wrote:
Quote:
According to Albert <Albert.Tollk... at (no spam) gmail.com>:

Depends on what you mean by secure. For my scenario is as below:
- I want to encrypt a message T.
- Send the encrypted file to anyone.
- Anyone can decrypt the file but they cannot create another encrypted
file.

If anyone can "decrypt" the message then its contents are basically
public, hence not confidential. It is quite inapropriate to speak of
"encryption" here.

The last few dozens of messages in this threads utterly demonstrate that
without a common terminology, otherwise intelligent human beings are
prone to fight. Let's detail things a little:

In the RSA mathematical core, there is a modulus (n) and two exponents
(usually named d and e). "d" and "e" are linked with a mathematical
relation which allows one to define two permutations: f(x) = x^d mod n,
and g(x) = x^e mod n. f() and g() are inverse of each other.

Note that we are still talking of permutations. There is no "key" yet.
A key is a parameter to a cryptosystem. From the core mathematical RSA
operation, two main cryptosystems are defined:
-- RSA asymmetric encryption, which can be used to encrypt confidential
messages;
-- RSA digital signatures, which are used to sign messages but without
any notion of confidentiality.

In both cryptosystems, the modulus is always known to everybody. One of
the exponents is made public, which means that everybody knows it. It is
_customary_ to use the name "e" for the exponent which is made public.
The other exponent is kept private. The "public key" is defined to be "n
and e". The "private key" is "d" _and everything which can be deduced
from the knowledge of "d" and the public key_. The last part is
important: basically, someone who knows n, e and d can compute the prime
factors of n (traditionally called p and q), and everything which can be
known about the modulus.

Hence the _definitions_ of the public and private keys in RSA are those
which are given by the text which _defines_ the RSA cryptosystems, i.e.
PKCS#1. In that text, the public key is n and e, and the private key
consists of a bunch of values, including n, d, p and q. The knownledge
of the private key is the knowledge of everything about the modulus.
Therefore it makes no sense to "make the private key public": that would
basically make everything public and there would be nothing private
anymore. This explains the comments from Pubkeybreaker: since the
definition of the private key includes everything about the modulus,
making it public means that everybody knows everything, and there is no
security anymore (whatever security properties were looked for).

Now you _could_ name the public exponent "d" and the private exponent
"e". That's just renaming the values. You could have named them "u" and
"v" too. The important parts are that knowing the private and public
parts is equivalent to knowing the factors, and everybody knows the
public part, since it is public(*). As a side note, the "private"
property (i.e. the property which states that the private part remains
private because it cannot be computed from the public elements) still
holds if the public exponent is short. Short exponents are good for
performance, hence it is customary to arrange for a very short "e" (**).
The private exponent, however, must not be too short (i.e., in order to
get a short "d", you have to use some internal structuring which can be
used later on to recover d from n and e, which defeats the property).

However, you had a real question, although you did not express it
directly. You have the RSA core: the two permutations. You believe
that you can make one public, by divulging the corresponding exponent
(and we traditionally choose the name "e" for that one), while keeping
the other permutation private. And that is correct. Then you have
a "message" expressed as an integer ("m") between 0 and n-1. We
can apply the public permutation (I called it g()) to that message m,
and since f() is the inverse of g(), then we know that f(g(m)) = m.
This leads to the RSA asymmetric encryption system. Your question was,
then: "what if I _first_ compute f(m), considering that g(f(m)) = m ?"
Well, the answer is: absolutely, this can also lead to a cryptosystem,
and it is called RSA digital signatures.

When you first apply the public operation g() on m, you get something
(g(m)) which can be converted back to the message m only through usage
of the private permutation f(), i.e. something which can be done only by
those who know the private key. Thus g(m) can be public without making m
public. It thus makes sense to use this in a system where m is
confidential; _only then_ can we speak of "encryption": a confidential
message is processed, so that the result can be transmitted "in the air"
without jeopardizing the confidentiality, and from that value an entity
which knows a specific secret (the private key) can recover the message.

If you first apply the private operation f() on m, then you get
something (f(m)) which _everybody_ can convert back to m by applying the
public permutation g(). Hence m is not confidential, and it would be
quite improper to state that m was "encrypted". What you get, however,
is a value (f(m)) which, when fed into g(), yields m, and producing such
a value for a given target m is _not_ possible to everybody; you have to
know f() for that. So what you have is a signature scheme: a proof that
the owner of the private permutation somehow acted upon the message m,
and this is verifiable by anybody using the public permutation.

(You may note that the first versions of PKCS#1 also got the terminology
a bit wrong, or at least used it in a confusing way. For instance, RSA
signatures are designated with names such as "md5WithRSAEncryption" in a
setup where there is no encryption at all since there is no confidential
message, and what is processed is really the hash of a file, and you
cannot recover the file from the hash anyway.)

A word of caution: going from the RSA mathematical core (the
permutations) to a cryptosystem (either encryption or signatures,
depending on whether you use the public or the private permutation
first) is a bit tricky, because the most naive ways have security
issues. PKCS#1 defines appropriate padding schemes, which have been
attacked and fixed and refined through decades of hard work by
cryptanalysts. And the resulting schemes are not identical: the scheme
for encryption is distinct from the scheme for signatures(***). In any
practical situations, you really should not get funky ideas, and you
should rely on PKCS#1 instead of inventing your own padding schemes.

--Thomas Pornin

(*) You may imagine something where both exponents are kept private,
by distinct entities. Apparently, from there you will get only a
creatively slow and inefficient symmetric encryption scheme, and you
really should consider using the AES instead.

(**) Some widely used implementations of the RSA cryptosystems are
actually unable to use public exponents which are not short. The
implementation in Windows CryptoAPI, used by many softwares including
Internet Explorer, insists on storing the public exponent in a 32-bit
word, and cannot handle RSA public keys where the public exponent is
bigger than that. In practice, this is not a problem.

(***) I do not know if we could define the same padding scheme for both
encryption and digital signatures (assuming that the input to digital
signatures is a hash of the signed message). A common padding scheme
would have to be randomized. When the "old" schemes (aka "v1.5") were
revised, two new padding schemes (OAEP and PSS) were defined, and they
are distinct from eachother.

Thanx a lot for all the explanations. My original idea wasn't to
create my own scheme, it was only to understand if the concept was
right.
Now I know that for what I was trying to do I should use digital
signatures. But knowing the underlying concepts helps a lot...
Most of the explanations here have been very helpful...
Thomas Pornin...
Posted: Tue May 13, 2008 6:43 am
Guest
According to Albert <Albert.Tollkuci at (no spam) gmail.com>:
Quote:
Depends on what you mean by secure. For my scenario is as below:
- I want to encrypt a message T.
- Send the encrypted file to anyone.
- Anyone can decrypt the file but they cannot create another encrypted
file.

If anyone can "decrypt" the message then its contents are basically
public, hence not confidential. It is quite inapropriate to speak of
"encryption" here.

The last few dozens of messages in this threads utterly demonstrate that
without a common terminology, otherwise intelligent human beings are
prone to fight. Let's detail things a little:

In the RSA mathematical core, there is a modulus (n) and two exponents
(usually named d and e). "d" and "e" are linked with a mathematical
relation which allows one to define two permutations: f(x) = x^d mod n,
and g(x) = x^e mod n. f() and g() are inverse of each other.

Note that we are still talking of permutations. There is no "key" yet.
A key is a parameter to a cryptosystem. From the core mathematical RSA
operation, two main cryptosystems are defined:
-- RSA asymmetric encryption, which can be used to encrypt confidential
messages;
-- RSA digital signatures, which are used to sign messages but without
any notion of confidentiality.

In both cryptosystems, the modulus is always known to everybody. One of
the exponents is made public, which means that everybody knows it. It is
_customary_ to use the name "e" for the exponent which is made public.
The other exponent is kept private. The "public key" is defined to be "n
and e". The "private key" is "d" _and everything which can be deduced
from the knowledge of "d" and the public key_. The last part is
important: basically, someone who knows n, e and d can compute the prime
factors of n (traditionally called p and q), and everything which can be
known about the modulus.

Hence the _definitions_ of the public and private keys in RSA are those
which are given by the text which _defines_ the RSA cryptosystems, i.e.
PKCS#1. In that text, the public key is n and e, and the private key
consists of a bunch of values, including n, d, p and q. The knownledge
of the private key is the knowledge of everything about the modulus.
Therefore it makes no sense to "make the private key public": that would
basically make everything public and there would be nothing private
anymore. This explains the comments from Pubkeybreaker: since the
definition of the private key includes everything about the modulus,
making it public means that everybody knows everything, and there is no
security anymore (whatever security properties were looked for).

Now you _could_ name the public exponent "d" and the private exponent
"e". That's just renaming the values. You could have named them "u" and
"v" too. The important parts are that knowing the private and public
parts is equivalent to knowing the factors, and everybody knows the
public part, since it is public(*). As a side note, the "private"
property (i.e. the property which states that the private part remains
private because it cannot be computed from the public elements) still
holds if the public exponent is short. Short exponents are good for
performance, hence it is customary to arrange for a very short "e" (**).
The private exponent, however, must not be too short (i.e., in order to
get a short "d", you have to use some internal structuring which can be
used later on to recover d from n and e, which defeats the property).


However, you had a real question, although you did not express it
directly. You have the RSA core: the two permutations. You believe
that you can make one public, by divulging the corresponding exponent
(and we traditionally choose the name "e" for that one), while keeping
the other permutation private. And that is correct. Then you have
a "message" expressed as an integer ("m") between 0 and n-1. We
can apply the public permutation (I called it g()) to that message m,
and since f() is the inverse of g(), then we know that f(g(m)) = m.
This leads to the RSA asymmetric encryption system. Your question was,
then: "what if I _first_ compute f(m), considering that g(f(m)) = m ?"
Well, the answer is: absolutely, this can also lead to a cryptosystem,
and it is called RSA digital signatures.

When you first apply the public operation g() on m, you get something
(g(m)) which can be converted back to the message m only through usage
of the private permutation f(), i.e. something which can be done only by
those who know the private key. Thus g(m) can be public without making m
public. It thus makes sense to use this in a system where m is
confidential; _only then_ can we speak of "encryption": a confidential
message is processed, so that the result can be transmitted "in the air"
without jeopardizing the confidentiality, and from that value an entity
which knows a specific secret (the private key) can recover the message.

If you first apply the private operation f() on m, then you get
something (f(m)) which _everybody_ can convert back to m by applying the
public permutation g(). Hence m is not confidential, and it would be
quite improper to state that m was "encrypted". What you get, however,
is a value (f(m)) which, when fed into g(), yields m, and producing such
a value for a given target m is _not_ possible to everybody; you have to
know f() for that. So what you have is a signature scheme: a proof that
the owner of the private permutation somehow acted upon the message m,
and this is verifiable by anybody using the public permutation.


(You may note that the first versions of PKCS#1 also got the terminology
a bit wrong, or at least used it in a confusing way. For instance, RSA
signatures are designated with names such as "md5WithRSAEncryption" in a
setup where there is no encryption at all since there is no confidential
message, and what is processed is really the hash of a file, and you
cannot recover the file from the hash anyway.)


A word of caution: going from the RSA mathematical core (the
permutations) to a cryptosystem (either encryption or signatures,
depending on whether you use the public or the private permutation
first) is a bit tricky, because the most naive ways have security
issues. PKCS#1 defines appropriate padding schemes, which have been
attacked and fixed and refined through decades of hard work by
cryptanalysts. And the resulting schemes are not identical: the scheme
for encryption is distinct from the scheme for signatures(***). In any
practical situations, you really should not get funky ideas, and you
should rely on PKCS#1 instead of inventing your own padding schemes.


--Thomas Pornin

(*) You may imagine something where both exponents are kept private,
by distinct entities. Apparently, from there you will get only a
creatively slow and inefficient symmetric encryption scheme, and you
really should consider using the AES instead.

(**) Some widely used implementations of the RSA cryptosystems are
actually unable to use public exponents which are not short. The
implementation in Windows CryptoAPI, used by many softwares including
Internet Explorer, insists on storing the public exponent in a 32-bit
word, and cannot handle RSA public keys where the public exponent is
bigger than that. In practice, this is not a problem.

(***) I do not know if we could define the same padding scheme for both
encryption and digital signatures (assuming that the input to digital
signatures is a hash of the signed message). A common padding scheme
would have to be randomized. When the "old" schemes (aka "v1.5") were
revised, two new padding schemes (OAEP and PSS) were defined, and they
are distinct from eachother.
 
Page 2 of 3    Goto page Previous  1, 2, 3  Next   All times are GMT - 5 Hours
The time now is Sat Oct 11, 2008 11:42 pm