You probably have your own closely guarded ssh key pair. Chances are good that it’s based on RSA, the default choice in ssh-keygen.<\/p>\n
RSA is a very simple and quite brilliant algorithm, and this article will show what a SSH RSA key pair contains, and how you can use those values to play around with and encrypt values using nothing but a calculator.<\/p>\n
RSA is based on primes, and the difficulty of factoring large numbers. This post is not meant as an intro to RSA, but here’s a quick reminder. I’ll use mostly the same symbols as Wikipedia<\/a>: you generate two large primes, p and q. Let \u03c6 = (p-1)(q-1). Pick a number e coprime to \u03c6, and let d \u2261 e^-1 mod \u03c6.<\/p>\n The public key is then (e, n), while your private key is (d, n). To encrypt a number\/message m, let the ciphertext c \u2261 m^e mod n. Then m \u2261 c^d mod n.<\/p>\n This is very simple modular arithmetic, but when you generate a key pair with ssh-keygen, you instead get a set of opaque and scary looking files, id_rsa and id_rsa.pub. Here’s a bit from the private key id_rsa (no passphrase):<\/p>\n How can we get our nice RSA parameters from this mess?<\/p>\n The easy way is with openssl: (I apologize in advance for all the data spam in the rest of the article).<\/p>\n Here, modulus is n, publicExponent is e, privateExponent is d, prime1 is p, prime2 is q, exponent1 is dP<\/sub> from the Wikipedia article<\/a>, exponent2 is dQ<\/sub> and coefficient is qInv<\/sub>.<\/p>\n Only the first three are strictly required to perform encryption and decryption. The latter three are for optimization and the primes are for verification.<\/p>\n It’s interesting to note that even though the private key from RSA’s point of view is (d,n), the OpenSSH private key file includes e, p, q and the rest as well. This is how it can generate public keys given the private ones. Otherwise, finding e given (d,n) is just as hard as finding d given (e,n), except e is conventionally chosen to be small and easy to guess for efficiency purposes.<\/p>\n If we have one of these hex strings on one line, without colons, and in uppercase, then bc can work on them and optionally convert to decimal.<\/p>\n We also need a power-modulo function, since b^e % m is unfeasibly slow if you go by way of b^e. Luckily, bc is programmable.<\/p>\n e=35<\/p>\n d=10150492579557375359576342890575270601332058572166512326253768176799\\ <\/em><\/strong><\/em><\/strong><\/p>\n <\/code> Yay, we’ve successfully encrypted and decrypted a value using real life RSA parameters!<\/p>\n What’s in the public key file, then?<\/p>\n This is a very simple file format, but I don’t know of any tools that will decode it. Simply base64-decode the middle string, and then read 4 bytes of length, followed by that many bytes of data. Repeat three times. You will then have key type, e and n, respectively.<\/p>\n Mine is 00 00 00 07, followed by 7 bytes “ssh-rsa”. Then 00 00 00 01, followed by one byte of 0x23 (35, our e). Finally, 00 00 00 61 followed by 0x61 = 97 bytes of our modulus n.<\/p>\n If you want to decode the private key by hand, base64-decode the middle bit. This gives you an ASN.1<\/a> encoded sequence of integers.<\/p>\n This is an annotated hex dump of parts of a base64-decoded private key<\/p>\n Here’s a bash script<\/a> that will decode a private key and output variable definitions and functions for bc, so that you can play around with it without having to do the copy-paste work yourself. It decodes ASN.1, and only requires OpenSSL if the key has a passphrase.<\/p>\n When run, and its output pasted into bc, you will have the variables n, e, d, p, q and a few more, functions encrypt(m) and decrypt(c), plus a verify() that will return 1 if the key is valid. These functions are very simple and transparent.<\/p>\n Enjoy!<\/p>\n","protected":false},"excerpt":{"rendered":" You probably have your own closely guarded ssh key pair. Chances are good that it’s based on RSA, the default choice in ssh-keygen. RSA is a very simple and quite brilliant algorithm, and this article will show what a SSH RSA key pair contains, and how you can use those values to play around with … Continue reading “What’s in a SSH RSA key pair?”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[5,4,22],"tags":[31,30,32],"class_list":["post-24","post","type-post","status-publish","format-standard","hentry","category-advanced-linux","category-linux","category-security","tag-encryption","tag-rsa","tag-ssh"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/24","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=24"}],"version-history":[{"count":0,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/24\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=24"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=24"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=24"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n-----BEGIN RSA PRIVATE KEY-----
\nMIIBygIBAAJhANj3rl3FhzmOloVCXXesVPs1Wa++fIBX7BCZ5t4lmMh36KGzkQmn
\njDJcm+O9nYhoPx6Bf+a9yz0HfzbfA5OpqQAyC\/vRTVDgHhGXY6HFP\/lyWQ8DRzCh
\ntsuP6eq9RYHnxwIBIwJhAKdf+4oqqiUWOZn\/\/vXrV3\/19LrGJYeU<\/code><\/p>\n <\/code><\/p>\n...
\n-----END RSA PRIVATE KEY-----
\n<\/code><\/p>\n
\nvidar@vidarholen ~\/.ssh $ openssl rsa -text -noout < id_rsa
\nPrivate-Key: (768 bit)
\nmodulus:
\n00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
\n54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
\n...
\npublicExponent: 35 (0x23)
\nprivateExponent:
\n00:a7:5f:fb:8a:2a:aa:25:16:39:99:ff:fe:f5:eb:
\n57:7f:f5:f4:ba:c6:25:87:94:48:64:93:fb:3d:a7:
\n...
\nprime1:
\n...
\nprime2:
\n...
\nexponent1:
\n...
\nexponent2:
\n...
\ncoefficient:
\n...
\n<\/code><\/p><\/blockquote>\n
\n# If you don't want to do this yourself, see end for a script
\nvidar@vidarholen ~\/.ssh $ { echo 'ibase=16'; cat | tr -d ':\\n ' | tr a-f A-F; echo; } | bc
\n
\n00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
\n54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
\n98:c8:77:e8:a1:b3:91:09:a7:8c:32:5c:9b:e3:bd:
\n....
\nCtrl-d to end input<\/em><\/strong>
\n13158045936463264355006370413708684112837853704660293756254884673628\\
\n63292...
\n<\/code><\/p><\/blockquote>\n
\nvidar@vidarholen ~\/.ssh $ bc
\nbc 1.06.94
\nCopyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
\nThis is free software with ABSOLUTELY NO WARRANTY.
\nFor details type `warranty'.<\/code><\/p>\n# Our powermod function:
\ndefine pmod(b,e,m) { if(e == 0 ) return 1; if(e == 1) return b%m; rest=pmod(b^2%m,e\/2,m); if((e%2) == 1) return (b*rest)%m else return rest; }
\n<\/em><\/strong><\/p>\n
\n#Define some variables (this time unabbreviated)
\nn=13158045936463264355006370413708684112837853704660293756254884673628\\
\n63292777770859554071108633728590995985653161363101078779505801640963\\
\n48597350763180843221886116453606059623113097963206649790257715468881\\
\n4303031148479239044926138311<\/em><\/strong><\/p>\n
\n23111571423234513140569517447770196903218153051479115016036905320557\\
\n80231250287900874055062921398102953416891810163858645414303785372309\\
\n5688315939617076008144563059<\/p>\n
\n# Encrypt the number 12345
\nc=pmod(12345, e, n)<\/em><\/strong>
\n
\n# Show the encrypted number
\nc<\/em><\/strong>
\n15928992191730477535088375321366468550579140816267293144554503305092\\
\n03492035891240033089011563910196180080894311697511846432462334632873\\
\n53515625<\/p>\n
\n#Decrypt the number
\npmod(c, d, n)
\n<\/em><\/strong>
\n12345
\n<\/code><\/p><\/blockquote>\nssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAGEA2PeuXcWHOY6WhUJdd6xU+zVZr758gFfsEJnm3iWYyHfoobORCaeMMlyb472diGg\/HoF\/5r3LPQd\/Nt8Dk6mpADIL+9FNUOAeEZdjocU\/+XJZDwNHMKG2y4\/p6r1FgefH vidar@vidarholen.spam<\/code><\/p>\n30 82 01 ca - Sequence, 0x01CA bytes\r\n 02 01: Integer, 1 byte\r\n 00\r\n 02 61: - Integer, 0x61 bytes (n).\r\n 00 d8 f7 ae 5d c5 87 39 8e 96 ... Same as from openssl!\r\n 02 01: - Integer, 1 byte, 0x23=35 (e)\r\n 23\r\n 02 61 - Integer, 0x61 bytes (d)\r\n 00 a7 5f fb 8a 2a aa 25 16 39 ...\r\n ...<\/pre>\n