Converting SSH2-RSA key to RSA numbers

[Dro Kulix]

I am working on a lightweight program that will use a simplistic
version of RSA for short encrypted transmissions. Of course it's a
dangerous thing to do when I'm not a crypto expert, but for the moment
that's beside the point. What I have in hand is a basic RSA
implementation that's already been written, which encrypts using an
encryption exponent E and a modulus M, and decrypts using a decryption
exponent D and the same modulus M. I assume, then, than E and M make
up the private key, D and M make up the public key.

Anyway, while I do have the encryption/decryption code, I don't have a
key generator to go with it. I decided that this wasn't going to be a
problem because there are plenty of good programs that will generate an
(unencrypted) OpenSSH SSH2 RSA key, and that I'd only have to find out
how to decode that format.

I've downloaded PuTTY's source to see if I could figure it out from
that. Turns out it's not trivial, so before I actually attempt to do
all the code chasing necessary to figure it out, I wanted to know if
anyone already knew enough about the key file format to save me some
trouble. Specifically, I'm looking to write a routine that converts
the key in an OpenSSH SSH2 RSA private key file into the aforementioned
E, D, and M.

If anyone has any suggestions, I'm all ears.

Thanks -- dro

[Simon Tatham]

Dro Kulix <peter...@gmail.com> wrote:
> I am working on a lightweight program that will use a simplistic
> version of RSA for short encrypted transmissions. Of course it's a
> dangerous thing to do when I'm not a crypto expert, but for the moment
> that's beside the point. What I have in hand is a basic RSA
> implementation that's already been written, which encrypts using an
> encryption exponent E and a modulus M, and decrypts using a decryption
> exponent D and the same modulus M. I assume, then, than E and M make
> up the private key, D and M make up the public key.

Other way round. The idea is that anyone can encrypt but only the
key owner can decrypt; so E is part of the _public_ key, and D is
the private key.

> I've downloaded PuTTY's source to see if I could figure it out from
> that. Turns out it's not trivial, so before I actually attempt to do
> all the code chasing necessary to figure it out, I wanted to know if
> anyone already knew enough about the key file format to save me some
> trouble. Specifically, I'm looking to write a routine that converts
> the key in an OpenSSH SSH2 RSA private key file into the aforementioned
> E, D, and M.

There's some documentation of the key file format in the source file
`import.c' in the PuTTY source base. The details of how the key is
_encrypted_ for storage aren't stated explicitly (you'd have to look
at the actual code), but if you're generating keys for other uses
then you'd probably make your life easier by generating unencrypted
ones in any case.

Essentially, the base64-encoded block in an OpenSSH key file is
encoded according to ASN.1, which is annoyingly complicated in
general but not _too_ many times worse than necessary for this job.
See the comment around line 538 of the current source.
--
Simon Tatham "Imagine what the world would be like if
<ana...@pobox.com> there were no hypothetical situations..."

[Dro Kulix]

I must not have been entirely awake when I wrote that first
paragraph... of course D is only in the private key...

Anyway, thanks. That lead will help.

[Unruh]

"Dro Kulix" <peter...@gmail.com> writes:

>I am working on a lightweight program that will use a simplistic
>version of RSA for short encrypted transmissions. Of course it's a
>dangerous thing to do when I'm not a crypto expert, but for the moment
>that's beside the point. What I have in hand is a basic RSA
>implementation that's already been written, which encrypts using an
>encryption exponent E and a modulus M, and decrypts using a decryption
>exponent D and the same modulus M. I assume, then, than E and M make
>up the private key, D and M make up the public key.

Uh, no, unless you want to be the only one who can encrypt and anyone in
the world can decrypt your messages. Usually people want anyone to be able
to encrypt and only you decrypt.

>Anyway, while I do have the encryption/decryption code, I don't have a
>key generator to go with it. I decided that this wasn't going to be a
>problem because there are plenty of good programs that will generate an
>(unencrypted) OpenSSH SSH2 RSA key, and that I'd only have to find out
>how to decode that format.

>I've downloaded PuTTY's source to see if I could figure it out from
>that. Turns out it's not trivial, so before I actually attempt to do
>all the code chasing necessary to figure it out, I wanted to know if
>anyone already knew enough about the key file format to save me some
>trouble. Specifically, I'm looking to write a routine that converts
>the key in an OpenSSH SSH2 RSA private key file into the aforementioned
>E, D, and M.

Look at teh source code for ssh-keygen. It will have all of the details.
That is the key generation program from openssh.

[Darren Tucker]

On 2005-04-02, Dro Kulix <peter...@gmail.com> wrote:
> Anyway, while I do have the encryption/decryption code, I don't have a
> key generator to go with it. I decided that this wasn't going to be a
> problem because there are plenty of good programs that will generate an
> (unencrypted) OpenSSH SSH2 RSA key, and that I'd only have to find out
> how to decode that format.

OpenSSL can read OpenSSH private keys (which are PEM format), with
something like:
$ openssl rsa -text -modulus -in keyfile

You could also use "openssl genrsa" to generate the keys.

--
Darren Tucker (dtucker at zip.com.au)
GPG key 8FF4FA69 / D9A3 86E9 7EEE AF4B B2D4 37C9 C982 80C7 8FF4 FA69
Good judgement comes with experience. Unfortunately, the experience
usually comes from bad judgement.

[Dro Kulix]

Before I begin: I already said I knew I was off when I said D is
public! Stop picking on me!

Thanks for all the input, everyone. Yesterday I was able to compose a
rough draft of a perl program that, through porting the BER
header-reading function from PuTTY and writing my own binary-to-bigint
conversion routine (it doesn't seem to be in there natively), was able
to extract the list of 9 bigints from both keys I exported from PuTTY
and keys I created with ssh-keygen. Of those, E, D, and N fit
perfectly with the encrypter/decrypter already written. Thanks!

I was curious to find out that all the keys generated from PuTTY seem
to have an encryption exponent of 0x25, which is prime, but the ones I
generated with ssh-keygen have 0x23, which is decidedly composite.

In any case, I wonder if either the fact that the encryption exponent
is not prime (OpenSSH) or somewhat small (OpenSSH and PuTTY) detracts
at all from the security of (vanilla) RSA. I'm already aware it
greatly improves encryption speed at the cost of more complexity for
the decrypter (which is fine--my decrypter's going to be binary, but
the encrypter is implemented in script), but I was wondering if that
carried any security implications. Making me more curious is the fact
that the sample data for the encrypter uses E = 0x10001, which is
larger (though not really very much) and still prime.

Any input?

Thanks -- dro

[Alan J Rosenthal]

"Dro Kulix" <peter...@gmail.com> writes:
>Before I begin: I already said I knew I was off when I said D is
>public! Stop picking on me!

Well, actually... it doesn't matter. It's symmetric. You keep one as
private key and publish the other; it doesn't matter which. Encrypt with one
and decrypt with the other, but it works in either direction. In fact, if you
want your correspondent to be able to verify that it's from you, you do it
both ways: encrypt with their public key and encrypt with your private key.
They then decrypt with your public key and decrypt with their private key.