Prev: Hash question
Next: A New/Old code Just For Fun
From: Yehudidedum on 20 Jul 2010 10:41
If I wanted to publish the decryption key and keep the encryption
key private (using something like RSA.)
The encryption key (private): E = (n,e)
The decryption key (public): D = (n,d)

(This may seem strange)
I would be able to encrypt messages that anyone with the public
key could decrypt.
I could use this as a form of validation, if the decrypted message
is valid (ie, makes sense in some way) then it could be seen as a
good , ie from the holder of the encryption key.

How difficult would it be to deduce E knowing D.

I do know that you can use RSA to generate a digital signature
the reason I am asking is that these seem to be quite large
about 320 bits for RSA(1024).and my messages have to
be very short - less than 50 bytes in general.

Thanks for any help.
Y
From: Tom St Denis on 20 Jul 2010 10:50
On Jul 20, 10:41 am, Yehudidedum <pete.mce...(a)metastate.co.uk> wrote:
> If I wanted to publish the decryption key and keep the encryption
> key private (using something like RSA.)
> The encryption key (private): E  = (n,e)
> The decryption key (public): D  = (n,d)
>
> (This may seem strange)
> I would be able to encrypt messages that anyone with the public
> key could decrypt.
> I could use this as a form of validation, if the decrypted message
> is valid (ie, makes sense in some way) then it could be seen as a
> good , ie from the holder of the encryption key.

Look up digital signatures. Stat.

> How difficult would it be to deduce E knowing D.

Usually 'e' is chosen to be small to optimize the operation. Knowing
both 'd' and 'e' allows one to factor.

> I do know that you can use RSA to generate a digital signature
> the reason I am asking is that these seem to be quite large
> about 320 bits for RSA(1024).and my messages have to
> be very short - less than 50 bytes in general.

Um? RSA signatures are at least as long as the modulus. So I don't
know where you got 320 from a 1024-bit key.

If you want a 50-byte signature you should look into ECC and EC-DSA.
A P-192 signature is 48 bytes (plus a few header bytes if you store it
as per the spec).

Tom
From: Gordon Burditt on 20 Jul 2010 11:55
>If I wanted to publish the decryption key and keep the encryption
>key private (using something like RSA.)
>The encryption key (private): E = (n,e)
>The decryption key (public): D = (n,d)
>
>(This may seem strange)
>I would be able to encrypt messages that anyone with the public
>key could decrypt.

Is confidentiality needed at all?

You can send the message in plaintext, signed with the private key.
Anyone with the public key can validate the signature is or is not
valid. Do some research on digital signatures. They are heavily
used in, for example, mobile phone apps where the applications must
be signed in order to be run.

>I could use this as a form of validation, if the decrypted message
>is valid (ie, makes sense in some way) then it could be seen as a
>good , ie from the holder of the encryption key.
>
>How difficult would it be to deduce E knowing D.

There are already estimates of that for RSA. If you're talking
about some other asymmetric encryption, you'll have to identify it
for anyone to give you an idea of its strength.

>I do know that you can use RSA to generate a digital signature
>the reason I am asking is that these seem to be quite large
>about 320 bits for RSA(1024).and my messages have to
>be very short - less than 50 bytes in general.

Well, 50 bytes = 400 bits. You can use RSA with shorter keys but
it will be less resistant to forgery.

What are you going to use this for? Some kind of licensing or DRM
scheme where the user of the device is presumed to be the adversary,
and he has physical access to the device?

There are two major types of attack against that:
(1) Replace the public key (which might be embedded in firmware) with
one which the attacker has generated (and then he can generate his
own license), or
(2) Find the conditional branch instruction which distinguishes between
a valid vs. invalid license and patch it into an unconditional
branch or a no-op.
neither of which involves attacking the signature directly.

From: Pubkeybreaker on 20 Jul 2010 12:04
On Jul 20, 10:41 am, Yehudidedum <pete.mce...(a)metastate.co.uk> wrote:
> If I wanted to publish the decryption key and keep the encryption
> key private (using something like RSA.)
> The encryption key (private): E  = (n,e)
> The decryption key (public): D  = (n,d)
>
> (This may seem strange)
> I would be able to encrypt messages that anyone with the public
> key could decrypt.
> I could use this as a form of validation, if the decrypted message
> is valid (ie, makes sense in some way) then it could be seen as a
> good , ie from the holder of the encryption key.
>
> How difficult would it be to deduce E knowing D.

That depends on the size of D. (or if E is very small), then
deducing E from D is easy.

>
> I do know that you can use RSA to generate a digital signature
> the reason I am asking is that these seem to be quite large
> about 320 bits for RSA(1024).

No. The signatures will be nearly 1024 bits for 1024-bit RSA.

>and my messages have to
> be very short - less than 50 bytes in general.

Use ECDSA.
From: Francois Grieu on 20 Jul 2010 12:15
Le 20/07/2010 16:41, Yehudidedum a �crit :
> If I wanted to publish the decryption key and keep the encryption
> key private (using something like RSA.)
> The encryption key (private): E = (n,e)
> The decryption key (public): D = (n,d)
>
> (This may seem strange)
> I would be able to encrypt messages that anyone with the public
> key could decrypt.
> I could use this as a form of validation, if the decrypted message
> is valid (ie, makes sense in some way) then it could be seen as a
> good , ie from the holder of the encryption key.

As pointed by Tom St Denis, you are reinventing RSA signature.

> How difficult would it be to deduce E knowing D.

Hard, if either
- E is big, random, and secret;
- you make a regular RSA key and permute E and D.

> I do know that you can use RSA to generate a digital signature
> the reason I am asking is that these seem to be quite large
> about 320 bits for RSA(1024).and my messages have to
> be very short - less than 50 bytes in general.

You loose. An RSA cryptogram (be it a signature or an encrypted message)
is at least the size of the modulus, that is 128 bytes
for 1024-bit modulus, which is often considered a bare minimum.

There are other (non-RSA) signature systems with shorter
cryptograms and keys, and probably higher security. On the other
hand, verifying an RSA or Rabin signature is simpler and faster
than in these other systems, when done with a standard CPU.

And the overhead of RSA/Rabin-signing a message can be reduced to
just over the size of a hash, if the message is not too small and
one accept that a portion of that is transformed, with the reverse
transform public for anyone with the public key and the will
to use it. This is "RSA signature with message recovery".
In a real application (Tachograph Smart Cards) using 1024-bit
modulus, signing adds 30 bytes (including 8 for identification of
the signer's key), and transforms 106 bytes of the message
(assumed to be at least that size).

Francois Grieu
 |  Next  |  Last
Pages: 1 2
Prev: Hash question
Next: A New/Old code Just For Fun