Score:3

How many Bits/Bytes is a public key, given its encoding

in flag

I am struggling to understand what the "bit/byte" size of a public key is, how you can work it out, and even what it means.

An example of a RSA public key is:

AAAAB3NzaC1yc2EAAAABJQAAAQB/nAmOjTmezNUDKYvEeIRf2YnwM9/uUG1d0BYsc8/tRtx+RGi7N2lUbp728MXGwdnL9od4cItzky/zVdLZE2cycOa18xBK9cOWmcKS0A8FYBxEQWJ/q9YVUgZbFKfYGaGQxsER+A0w/fX8ALuk78ktP31K69LcQgxIsl7rNzxsoOQKJ/CIxOGMMxczYTiEoLvQhapFQMs3FL96didKr/QbrfB1WT6s3838SEaXfgZvLef1YB2xmfhbT9OXFE3FXvh2UPBfN+ffE7iiayQf/2XR+8j4N4bW30DiPtOQLGUrH1y5X/rpNZNlWW2+jGIxqZtgWg7lTy3mXy5x836Sj/6L

How do I work out the bitlength of this key? There are 368 characters, so is that the bitength? That would then mean that this is a 46 byte system, right? I barely grasp what that means, and I've sank a week or two into Wikipedia articles, YouTube tutorials and more. These often talk as if you understand what they mean, so I don't have much to go off of. If someone could explain the logic I am missing here, that would help a lot.

I understand that an 8 bit block is 1 byte, that is to say that we have a length of 8 characters that can be 1 or 0. But I have no idea how that would relate to the above?

Ultimately, I have a different public key that I wanted to work out the size for. Say I have two sets of integers, $S_1$ and $S_2$. Their sizes are 100 and 150 respectively. These two make up my public key. This is vastly different than the above example, so how do I work out the bit size? Or am I asking the wrong thing here? Really I want to know how much storage on a computer such a key would take up. Say I had 100 sets, each with 1000 terms. How large a "file" would that public key be? But I want to try to "understand" what bits/bytes even means in the first place.

Any clarifications would be greatly appreciate.

Score:6
gb flag

Lot of questions here. I try to break it down quite simple and answer your initial question.

What you have posted is a base64 encoding of an ssh-rsa public key. So its basically not really readable to humans. If you decode this string, you can have a look at it byte-wise. I will show you the first several bytes of your example, trying to explain what they mean:

00000000  00 00 00 07 73 73 68 2d  72 73 61 00 00 00 01 25  |....ssh-rsa....%|
00000010  00 00 01 00 7f 9c 09 8e  8d 39 9e cc d5 03 29 8b  |.........9....).|
00000020  c4 78 84 5f d9 89 f0 33  df ee 50 6d 5d d0 16 2c  |.x._...3..Pm]..,|
  • The first four bytes are 0x00 0x00 0x00 0x07, indicating that the next field you have to read is seven bytes long
  • then you have the next seven bytes: 0x73, 0x73, .... 0x61, which translate to "ssh-rsa".
  • the next four bytes are 0x00 0x00 0x00 0x01, indicating that the next one byte describes your public exponent
  • then you have 0x25, which is your public exponent
  • the next four bytes are 0x00 0x00 0x01 0x00, indicating that your public modulus is 0x0100 byte long (which translates to 256 bytes - which translates to 2048 bits)
  • and then you have your public modulus

Thus you know that in this case your public key modulus is 2048 bit. Note that RSA keys can vary in size. For further information you can probably take a look at this page, which describes the structure of RSA keys and probably the wikipedia page of RSA in general.

MeBadMaths avatar
in flag
I thought that RSA public key looked entirely alien to me. Thank you for clearing that up and for the two links. That first one isn't one I've read, I will have a look at it now. You've answered a few of my initial questions, which I appreciate a lot. You have said that this is 256 bytes - does that mean if I had stored that public key on, say, a word document, the file size would be 256 bytes?
Maarten Bodewes avatar
in flag
No, the "size" of an RSA key is determined by the bit size modulus alone. A public key can be encoded in a lot of different ways, but generally the public exponent is also stored, so in that case the size will be larger than 256 bytes. In other words: the **encoded** key size depends on the key size, the meta data stored with they key and the type of encoding used.
MeBadMaths avatar
in flag
Okay, so the example I gave was an encoded key? Hence it would be larger because the encoding adds extra information that must be stored? I think that makes sense, thank you!
MeBadMaths avatar
in flag
So to work out the byte sizes of the RSA public key I provided, it requires details that are encoded as well as details from the encoding process itself. This is therefore not transferable to other public keys for other systems. I assume that working out the size of public keys is not the same for all public keys? Therefore, the big question I have, is what is the size of the public key corresponding to sets in my post? That's my main goal, and I was probably a bit naïve about how easy this would be haha. Thanks for the replies so far!
BlueRaja - Danny Pflughoeft avatar
cn flag
@MeBadMaths: The base64 encoding also inflates the size a bit. Each character in the string you pasted takes 8-bits to store _(potentially more, depending on the encoding of the characters!)_, but it only represents one of 64 = 2^6 = "6 bits worth of" values. So why use base64 if it's so wasteful? It's done because a raw key would look like a bunch of gibberish symbols in a text-editor, and would not copy+paste correctly, while its base64 representation can.
MeBadMaths avatar
in flag
@BlueRaja-DannyPflughoeft That makes things more clear. So each character corresponds to 6-bits of storage, since its base64. It's stored as 8-bits, wasting 2 bits. So say my public key was two groups of numbers; $\{0,1,6,7\}$ and $\{0,2,4\}$. Turning them into binary, then into base64, I think the sets turn into AAEGBw= (Might be wrong with the padding) and AAIE. Each character is 8-bits=1byte (wasting 2 bits), so the total size is 7byte and 4 byte respectively. Is that right? I might not be accounting for the symbol { }, so just the numerical values
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.