InCTF 2014 - Crypto 300

This is also a RSA challenge which is more interesting, given a RSA-704 bit. Factors are found in the wiki. I used openssl to finish, this challenge. 
root@Vijay:# openssl rsa -inform PEM -text -pubin -in publickey.pem -modulus

Public-Key: (704 bit)

Modulus:
    00:e1:34:18:93:fe:6e:68:16:ce:c8:a9:70:a3:9c:
    00:fa:54:7c:7d:a2:cd:ed:ab:0a:62:b9:1c:46:51:
    a8:3f:96:38:0b:cf:ae:e2:6f:7e:86:61:07:90:63:
    89:42:1b:1e:68:d0:a1:7a:ad:c9:87:0b:98:58:e9:
    56:28:6e:39:99:e9:8c:ec:98:81:53:4a:c7:72:ae:
    78:f5:e8:ab:a1:e2:f8:d3:03:95:77:02:9d:87

Exponent: 65537 (0x10001)

Modulus=E1341893FE6E6816CEC8A970A39C00FA547C7DA2CDEDAB0A62B91C4651A83F96380BCFAEE26F7E866107906389421B1E68D0A17AADC9870B9858E956286E3999E98CEC9881534AC772AE78F5E8ABA1E2F8D3039577029D87

writing RSA key
-----BEGIN PUBLIC KEY-----
MHQwDQYJKoZIhvcNAQEBBQADYwAwYAJZAOE0GJP+bmgWzsipcKOcAPpUfH2ize2r
CmK5HEZRqD+WOAvPruJvfoZhB5BjiUIbHmjQoXqtyYcLmFjpVihuOZnpjOyYgVNK
x3KuePXoq6Hi+NMDlXcCnYcCAwEAAQ==
-----END PUBLIC KEY-----


source: http://en.wikipedia.org/wiki/RSA_numbers#RSA-704

RSA-704 = 74037563479561712828046796097429573142593188889231289084936232638972765034
          02826627689199641962511784399589433050212758537011896809828673317327310893
          0900552505116877063299072396380786710086096962537934650563796359

RSA-704 = 90912135295978188784406583026004374858926083103283587204285121689604115286
          40933367824950788367956756806141
        × 81438592591100452657278091262844293358778990021676278832009141724293243601
          33004116702003240828777970252499
We got the factors and finally we need a private key to decrypt the cipher. Question is how to make a private key with known factors and exponents. I googled and found the answer. 
Sorry Guys this solution I got from the 
http://stackoverflow.com/questions/5244129/openssl-use-rsa-private-key-to-generate-public-key.
I have just pasted it to save my time.

One way to do this is to generate a DER encoded key using
 OpenSSL's asn1parse command's -genconf option.

You'll need to construct an input file for 
asn1parse -genconf to produce an RSA key in the standard format (per RFC 3447). 

The syntax for asn1parse -genconf is given here: 
http://www.openssl.org/docs/crypto/ASN1_generate_nconf.html and indeed, 
it already has an example for constructing an RSA key.

You need to calculate a few more values 
specifically, 
d mod (p-1), 
d mod (q-1) and q^-1 mod p. 

For the values of p, q, d you gave, these are:

d mod(p-1) = 23 mod 16 = 7

d mod(q-1) = 23 mod 10 = 3

q^-1 mod p = 14

Put this all together into a text file in the appropriate format and save as key.der:

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:187
pubExp=INTEGER:7
privExp=INTEGER:23
p=INTEGER:17
q=INTEGER:11
e1=INTEGER:7
e2=INTEGER:3
coeff=INTEGER:14

To construct the binary DER file:

#openssl asn1parse -genconf key.der -out newkey.der

You can then run this through OpenSSL's rsa command to confirm:

#openssl rsa -in newkey.der -inform der -text -check

Which should output:

Private-Key: (8 bit)
modulus: 187 (0xbb)
publicExponent: 7 (0x7)
privateExponent: 23 (0x17)
prime1: 17 (0x11)
prime2: 11 (0xb)
exponent1: 7 (0x7)
exponent2: 3 (0x3)
coefficient: 14 (0xe)
RSA key ok
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MBwCAQACAgC7AgEHAgEXAgERAgELAgEHAgEDAgEO
-----END RSA PRIVATE KEY-----
I have done these procedures and got the private.pem file successfully, but stucked with one error. But finally solved it. 
root@Vijay:# cat c4.der 

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359
pubExp=INTEGER:65537
privExp=INTEGER:33307131606083860709359654688809620595435784183304180784765475180353602262817269247014766169336517530471801339770560112997370264392886185538231911908428012730752492181217073681726139624557304859252988692991966953
p=INTEGER:9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141
q=INTEGER:8143859259110045265727809126284429335877899002167627883200914172429324360133004116702003240828777970252499
e1=INTEGER:2507619619063121166143884830494348359437885170602953149963932045688654640939349565744108448682844107798413
e2=INTEGER:1427912274691144393983219474039616972070325731020770129939754714976049654733789314509707787057135475474487
coeff=INTEGER:8477527216127115374020752451819578914339836291401467007371057661280467726317233563985936543959908245049748


root@Vijay:# openssl asn1parse -genconf  c4.der -out new.der

    0:d=0  hl=4 l= 422 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=2 l=  89 prim: INTEGER           :E1341893FE6E6816CEC8A970A39C00FA547C7DA2CDEDAB0A62B91C4651A83F96380BCFAEE26F7E866107906389421B1E68D0A17AADC9870B9858E956286E3999E98CEC9881534AC772AE78F5E8ABA1E2F8D3039577029D87
   98:d=1  hl=2 l=   3 prim: INTEGER           :010001
  103:d=1  hl=2 l=  88 prim: INTEGER           :654FD57AC6AC8EA12C17B3BA5BB033F46A0BB34D898CD13493E328E82D961E3D0B2BAD1BC4FC599444946D8CB176B386D0643BC6AC269EF25A1AA31B94A9E6F95634E9DFA61E97CBACFF11FEF97F75D7CF3135C4D185FEE9
  193:d=1  hl=2 l=  45 prim: INTEGER           :FDB0A3E5B29553D7DF414F417C734CF5A5ED9EC055DD5AD26285D681E088194665574C0DA4CE3FA1E5E239FD
  240:d=1  hl=2 l=  45 prim: INTEGER           :E3410D84EE816CEBE8C96F5374ABF43F2B4DC4ECEDFEC6582AFDC8CA19D2D14F80495FD9E2EE7356A787BAD3
  287:d=1  hl=2 l=  44 prim: INTEGER           :45F99C2BB687A3F9CE75F8438AED4ED40F31ACF1467DE91850DEB3DD5D2E8D3232AFD2A58CC8EB1A600B778D
  333:d=1  hl=2 l=  44 prim: INTEGER           :27D889294CB46EC7B26A5755B7B84ABC24B89F15B7E91B17EC79D111F6932B56183545542BE10962213FC037
  379:d=1  hl=2 l=  45 prim: INTEGER           :EC90AABF6672CF701FA8D1D590FA6E24611B40B25AD67CAACED3B73DE85B2DF5EEE131D3693E717EA5401194
  
  
root@Vijay:# openssl rsa -in new.der -inform der -text -check -out private.pem

Private-Key: (704 bit)
modulus:
    00:e1:34:18:93:fe:6e:68:16:ce:c8:a9:70:a3:9c:
    00:fa:54:7c:7d:a2:cd:ed:ab:0a:62:b9:1c:46:51:
    a8:3f:96:38:0b:cf:ae:e2:6f:7e:86:61:07:90:63:
    89:42:1b:1e:68:d0:a1:7a:ad:c9:87:0b:98:58:e9:
    56:28:6e:39:99:e9:8c:ec:98:81:53:4a:c7:72:ae:
    78:f5:e8:ab:a1:e2:f8:d3:03:95:77:02:9d:87
publicExponent: 65537 (0x10001)
privateExponent:
    65:4f:d5:7a:c6:ac:8e:a1:2c:17:b3:ba:5b:b0:33:
    f4:6a:0b:b3:4d:89:8c:d1:34:93:e3:28:e8:2d:96:
    1e:3d:0b:2b:ad:1b:c4:fc:59:94:44:94:6d:8c:b1:
    76:b3:86:d0:64:3b:c6:ac:26:9e:f2:5a:1a:a3:1b:
    94:a9:e6:f9:56:34:e9:df:a6:1e:97:cb:ac:ff:11:
    fe:f9:7f:75:d7:cf:31:35:c4:d1:85:fe:e9
prime1:
    00:fd:b0:a3:e5:b2:95:53:d7:df:41:4f:41:7c:73:
    4c:f5:a5:ed:9e:c0:55:dd:5a:d2:62:85:d6:81:e0:
    88:19:46:65:57:4c:0d:a4:ce:3f:a1:e5:e2:39:fd
prime2:
    00:e3:41:0d:84:ee:81:6c:eb:e8:c9:6f:53:74:ab:
    f4:3f:2b:4d:c4:ec:ed:fe:c6:58:2a:fd:c8:ca:19:
    d2:d1:4f:80:49:5f:d9:e2:ee:73:56:a7:87:ba:d3
exponent1:
    45:f9:9c:2b:b6:87:a3:f9:ce:75:f8:43:8a:ed:4e:
    d4:0f:31:ac:f1:46:7d:e9:18:50:de:b3:dd:5d:2e:
    8d:32:32:af:d2:a5:8c:c8:eb:1a:60:0b:77:8d
exponent2:
    27:d8:89:29:4c:b4:6e:c7:b2:6a:57:55:b7:b8:4a:
    bc:24:b8:9f:15:b7:e9:1b:17:ec:79:d1:11:f6:93:
    2b:56:18:35:45:54:2b:e1:09:62:21:3f:c0:37
coefficient:
    00:ec:90:aa:bf:66:72:cf:70:1f:a8:d1:d5:90:fa:
    6e:24:61:1b:40:b2:5a:d6:7c:aa:ce:d3:b7:3d:e8:
    5b:2d:f5:ee:e1:31:d3:69:3e:71:7e:a5:40:11:94

RSA key ok

writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIBpgIBAAJZAOE0GJP+bmgWzsipcKOcAPpUfH2ize2rCmK5HEZRqD+WOAvPruJv
foZhB5BjiUIbHmjQoXqtyYcLmFjpVihuOZnpjOyYgVNKx3KuePXoq6Hi+NMDlXcC
nYcCAwEAAQJYZU/VesasjqEsF7O6W7Az9GoLs02JjNE0k+Mo6C2WHj0LK60bxPxZ
lESUbYyxdrOG0GQ7xqwmnvJaGqMblKnm+VY06d+mHpfLrP8R/vl/ddfPMTXE0YX+
6QItAP2wo+WylVPX30FPQXxzTPWl7Z7AVd1a0mKF1oHgiBlGZVdMDaTOP6Hl4jn9
Ai0A40ENhO6BbOvoyW9TdKv0PytNxOzt/sZYKv3IyhnS0U+ASV/Z4u5zVqeHutMC
LEX5nCu2h6P5znX4Q4rtTtQPMazxRn3pGFDes91dLo0yMq/SpYzI6xpgC3eNAiwn
2IkpTLRux7JqV1W3uEq8JLifFbfpGxfsedER9pMrVhg1RVQr4QliIT/ANwItAOyQ
qr9mcs9wH6jR1ZD6biRhG0CyWtZ8qs7Ttz3oWy317uEx02k+cX6lQBGU
-----END RSA PRIVATE KEY-----


root@Vijay:# openssl rsa -inform PEM -text  -in private.pem 

Private-Key: (704 bit)
modulus:
    00:e1:34:18:93:fe:6e:68:16:ce:c8:a9:70:a3:9c:
    00:fa:54:7c:7d:a2:cd:ed:ab:0a:62:b9:1c:46:51:
    a8:3f:96:38:0b:cf:ae:e2:6f:7e:86:61:07:90:63:
    89:42:1b:1e:68:d0:a1:7a:ad:c9:87:0b:98:58:e9:
    56:28:6e:39:99:e9:8c:ec:98:81:53:4a:c7:72:ae:
    78:f5:e8:ab:a1:e2:f8:d3:03:95:77:02:9d:87
publicExponent: 65537 (0x10001)
privateExponent:
    65:4f:d5:7a:c6:ac:8e:a1:2c:17:b3:ba:5b:b0:33:
    f4:6a:0b:b3:4d:89:8c:d1:34:93:e3:28:e8:2d:96:
    1e:3d:0b:2b:ad:1b:c4:fc:59:94:44:94:6d:8c:b1:
    76:b3:86:d0:64:3b:c6:ac:26:9e:f2:5a:1a:a3:1b:
    94:a9:e6:f9:56:34:e9:df:a6:1e:97:cb:ac:ff:11:
    fe:f9:7f:75:d7:cf:31:35:c4:d1:85:fe:e9
prime1:
    00:fd:b0:a3:e5:b2:95:53:d7:df:41:4f:41:7c:73:
    4c:f5:a5:ed:9e:c0:55:dd:5a:d2:62:85:d6:81:e0:
    88:19:46:65:57:4c:0d:a4:ce:3f:a1:e5:e2:39:fd
prime2:
    00:e3:41:0d:84:ee:81:6c:eb:e8:c9:6f:53:74:ab:
    f4:3f:2b:4d:c4:ec:ed:fe:c6:58:2a:fd:c8:ca:19:
    d2:d1:4f:80:49:5f:d9:e2:ee:73:56:a7:87:ba:d3
exponent1:
    45:f9:9c:2b:b6:87:a3:f9:ce:75:f8:43:8a:ed:4e:
    d4:0f:31:ac:f1:46:7d:e9:18:50:de:b3:dd:5d:2e:
    8d:32:32:af:d2:a5:8c:c8:eb:1a:60:0b:77:8d
exponent2:
    27:d8:89:29:4c:b4:6e:c7:b2:6a:57:55:b7:b8:4a:
    bc:24:b8:9f:15:b7:e9:1b:17:ec:79:d1:11:f6:93:
    2b:56:18:35:45:54:2b:e1:09:62:21:3f:c0:37
coefficient:
    00:ec:90:aa:bf:66:72:cf:70:1f:a8:d1:d5:90:fa:
    6e:24:61:1b:40:b2:5a:d6:7c:aa:ce:d3:b7:3d:e8:
    5b:2d:f5:ee:e1:31:d3:69:3e:71:7e:a5:40:11:94

writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIBpgIBAAJZAOE0GJP+bmgWzsipcKOcAPpUfH2ize2rCmK5HEZRqD+WOAvPruJv
foZhB5BjiUIbHmjQoXqtyYcLmFjpVihuOZnpjOyYgVNKx3KuePXoq6Hi+NMDlXcC
nYcCAwEAAQJYZU/VesasjqEsF7O6W7Az9GoLs02JjNE0k+Mo6C2WHj0LK60bxPxZ
lESUbYyxdrOG0GQ7xqwmnvJaGqMblKnm+VY06d+mHpfLrP8R/vl/ddfPMTXE0YX+
6QItAP2wo+WylVPX30FPQXxzTPWl7Z7AVd1a0mKF1oHgiBlGZVdMDaTOP6Hl4jn9
Ai0A40ENhO6BbOvoyW9TdKv0PytNxOzt/sZYKv3IyhnS0U+ASV/Z4u5zVqeHutMC
LEX5nCu2h6P5znX4Q4rtTtQPMazxRn3pGFDes91dLo0yMq/SpYzI6xpgC3eNAiwn
2IkpTLRux7JqV1W3uEq8JLifFbfpGxfsedER9pMrVhg1RVQr4QliIT/ANwItAOyQ
qr9mcs9wH6jR1ZD6biRhG0CyWtZ8qs7Ttz3oWy317uEx02k+cX6lQBGU
-----END RSA PRIVATE KEY-----


(to get the public key part out from the private key)

root@Vijay:# openssl rsa -in private.pem -out publickey.pem -outform PEM -pubout
writing RSA key

root@Vijay:# cat pub.key publickey.pem 

-----BEGIN PUBLIC KEY-----
MHQwDQYJKoZIhvcNAQEBBQADYwAwYAJZAOE0GJP+bmgWzsipcKOcAPpUfH2ize2r
CmK5HEZRqD+WOAvPruJvfoZhB5BjiUIbHmjQoXqtyYcLmFjpVihuOZnpjOyYgVNK
x3KuePXoq6Hi+NMDlXcCnYcCAwEAAQ==
-----END PUBLIC KEY-------

root@Vijay:# file publickey.pem 
publickey.pem: ASCII text
==================================================================================================================

root@Vijay:# openssl enc -in cipher -out binarytext -d 

root@Vijay:# openssl rsautl -decrypt -in binarytext -out plaintext -inkey private.pem

RSA operation error
3074128024:error:0406506C:rsa routines:RSA_EAY_PRIVATE_DECRYPT:data greater than mod len:rsa_eay.c:523:

( I got stucked so I decided to test my own msg with those keys )

root@Vijay:# echo 'my first OPENSSL + RSA Try' > msg

root@Vijay:# openssl rsautl -encrypt -inkey publickey.pem -pubin -in msg -out msg.enc

root@Vijay:# file msg.enc 
msg.enc: data

root@Vijay:# cat msg.enc
���k��l=��  ۶�R�
                O.َ/� ��(nJ���=�o}��B6�6 b�I&��;M  & � (�[\�i� 5�ў���E��.Sԧ��U 
                

root@Vijay:# openssl rsautl -decrypt -inkey private.pem -in msg.enc -out msg_original

( I got my message without an error)
 
root@Vijay:# cat msg_original
my first OPENSSL + RSA Try

( Again I tried for the challenge)

root@Vijay:# head -32c msg.sha256 | openssl rsautl -decrypt -inkey private.pem -in cipher -out decrypted.txt

head: cannot open `msg.sha256' for reading: No such file or directory
RSA operation error
3073902744:error:0407106B:rsa routines:RSA_padding_check_PKCS1_type_2:block type is not 02:rsa_pk1.c:190:
3073902744:error:04065072:rsa routines:RSA_EAY_PRIVATE_DECRYPT:padding check failed:rsa_eay.c:616:

root@Vijay:# head -32c cipher.sha256 | openssl rsautl -decrypt -inkey private.pem -in cipher -out decrypted.txt
head: cannot open `cipher.sha256' for reading: No such file or directory
RSA operation error
3074226328:error:0407106B:rsa routines:RSA_padding_check_PKCS1_type_2:block type is not 02:rsa_pk1.c:190:
3074226328:error:04065072:rsa routines:RSA_EAY_PRIVATE_DECRYPT:padding check failed:rsa_eay.c:616:

( Finally got this Solution from http://pastebin.com/S3SHX5Rz)

root@Vijay:# perl -e '$a = `cat cipher`; print "".reverse($a);' > cipher.r
 
root@Vijay:# head -256c cipher | openssl rsautl -decrypt -raw -inkey private.pem -out flag
 
root@Vijay:# cat flag
Mere use of RSA does not guarantee security. The flag for this level is brokenrsakey
Useful Links:
  http://www.openssl.org/docs/apps/rsa.html
http://www.devco.net/archives/2006/02/13/public_-_private_key_encryption_using_openssl.php

Comments

Post a Comment

Popular posts from this blog

Python Speech recognition for Mac OS X

Hi Folks, I have been been searching for the    Python Speech recognition package especially for Mac OS.  I am not happy with the search results. Finally I got  https://pypi.python.org/pypi/SpeechRecognition/ (SpeechRecognition works only for the Linux distributions and Windows.) But I made it working for the Mac OS X by using flac.  Following are the instructions to make it run and modified code,  Prerequisite: Install Xcode in Unix Development mode Install Xcode - Command Line tools (Type ' xcode-select —install' in the terminal ) Install Port or Brew ( port    [or]   Brew   ) sudo brew install portaudio  [or]  sudo port install portaudio (for loading mic drivers) sudo pip install pyaudio [or] sudo easy_install install pyaudio (Mic Sources) sudo pip install SpeechRecognition [or] sudo easy_install install SpeechRecognition sudo port install flac Once you have finished w...
Read more

Baby Step Giant Step Algorithm Python Code

#Baby Step Giant Step DLP problem y = a**x mod n #Example 70 = 2**x mod 131 y = 70 a = 2 n = 131 s = floor(sqrt(n)) A = [] B = [] for r in range(0,s): value = y*(a^r) % n A.append(value) for t in range(1,s+1): value = a^(t*s) % n B.append(value) print A print B x1,x2 =0,0 for r in A: for t in B: if r == t: x1 = A.index(r) x2 = B.index(t) print x1,x2 break print 'the value of x is ', ((x2+1)*s - x1) % n # Answer
Read more

Simple Automation using Python - Atomac in Mac OS X

Image
The Product Automation in MAC OS X is quite easy if we have enough knowledge in the following languages and tools  Bash Scripts  Apple Scripts  Python especially ATOMac Knowledge in Accessibility. For more understanding of the LDTP: http://download.freedesktop.org/ldtp/doc/ldtp-tutorial.pdf LDTP - Tutorial is written by  Nagappan Alagappan. He has given the clear idea and architecture of the LDTP and its working. I have used the contents from the tutorial for knowledge sharing. Following are the few information and contents from  the LDTP - Tutorial. Few interesting key points, Linux Desktop Testing Project (LDTP) i s aimed at producing high quality test automation framework and cutting-edge tools that can be used to test GNU/Linux Desktop and improve it.  It uses the Accessibility libraries to poke through the application's user interface.  This idea has been extended to Microsoft Windows as Cobra , Mac OS X as ATOMa...
Read more