My team solved Vigenere3d, Run me!, putchar music, SHA-1 is dead and Thank you for playing! and got 500 points.

putchar music

I searched putchar music then found Creating music in one line of C code.
/dev/dsp is one of driver used in OSS (Open Sound System) but it is old slightly.
Instead of it, we can use ALSA installed in Ubuntu 17.10 by default.

1
2
3
$ cat a.c
main(){int t,i,j; unsigned char p[]="###<f_YM\204g_YM\204g_Y_H #<f_YM\204g_YM\204g_Y_H #+-?[WKAMYJ/7 #+-?[WKgH #+-?[WKAMYJ/7hk\206\203tk\\YJAfkkk";for(i=0;t=1;i=(i+1)%(sizeof(p)-1)){double x=pow(1.05946309435931,p[i]/6+13);for(j=1+p[i]%6;t++%(8192/j);)putchar(t>>5|(int)(t*x));}}
$ gcc a.c -lm > /dev/null 2>&1; ./a.out | aplay

Ps and Qs

ref: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation

In this problem, pub1 and pub2 are using the same prime number.
Therefore we can calcurate p and q by p = gcd(pub1, pub2) q = pub1 / p and create the private key by following steps:

  1. Choose two distinct prime numbers p and q.
  2. Compute n = pq.
  3. Compute λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1), where λ is Carmichael’s totient function. This value is kept private.
  4. Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime.
  5. Determine d as d ≡ e−1 (mod λ(n)); i.e., d is the modular multiplicative inverse of e (modulo λ(n)).

p, q and e are already given.
d satisfy a formula e * d (mod λ(n)) = 1 so we can calculate it by using Extended Euclidean algorithm.

Decryption

Alice can recover m from c by using her private key exponent d by computing
c^d ≡ (m^e)^d ≡ m (mod n)
Given m, she can recover the original message M by reversing the padding scheme.

Now c and d are known, so we can decrypt the cipher.

1
2
3
4
5
6
7
8
$ openssl rsa -text -modulus -pubin < pub1.pub 2>&1 | grep Exponent | awk '{print $2}'
65537
$ openssl rsa -text -modulus -pubin < pub1.pub 2>&1 | grep Modulus= | awk -F= '{print "0x"$2}'
0xCFCFBBEEA7DF143A8AC208B1AA1D2F86545AC4CB588C94A3FB1C14AD91A4F0B936157C5A4B869C18A8B864F4726BF8FCDC020CB41042BAC96784AB7D03F9374947EFB0BC3D665831974340159FFC3DB7C8E74B6390FDA6EEC30B81C6FF624E8D3F5B17BFB7A5C7FFD8ECF4E6518B393ABEFDDD0FAEBA4308746BA63F8106B59D7E058943A00131A7D4E538C464B270577647EDBC478CC1CE9585EFE877305B3A7C2E7C44DB5475EDDADC345A2C90A946771CAC0A454CDBCB461F2840E7613C83E9CECC94037FA09BB9DAA3F180562C01DF0BE6C51F0C06E8F0E2D6E1A5E50D0A28C3881140770A9F45934146B7F359B939CE23F0FA507A6F4E454571430952003C20F1D97A67140B6E5FCBFB3B376E4E24969AEB1D489CFC72AF4F15A4788A1AA97C89756D1D4D94AA47E7CD3A81AECB92448CC92C77D2EF576AA0DBC1350862ACCDDADDBCE80357F0CD5B854DD0F8C4627FE4B718B24ECFE11ED24C3BE22F00643BBED4EE5E345AF176E5B76D23A2F80E0EC6F34E5718C62A70FE5570C28B807B44F22EADEBD9B5FF906F6A85BE88C0C8F6E5F880A51F17F84DB1C2EEFEA8AF34040444CED1A37DF0E4F5F72CC3F50B7E427C8C2D8B6186EAD762F0C444B3CA3A0103ED12A93BCE9CAE7479A229EBBC0A648EAA6F97E5051A66EB09EBD7348E92F75F125EBDC367E2A7D1DA7759D41FAE2E2635BF4B7A7F91BECAB3AC7D05BD
$ openssl rsa -text -modulus -pubin < pub2.pub 2>&1 | grep Modulus= | awk -F= '{print "0x"$2}'
0xBB33CC7FCC8ECAF3BF9ED95C583792E1EC6B80EE875EC2064DBCF07595C8344923BF536524D4E0A75574C7798C73B197DD2B1B42054B1E49CB45FBF04E6F114CF8A365C3DF3645524F778268038A3FA26802E9D1EDBFBB5EDFB5A0C375370D7F10F57DABBD4F771DAD3632F01B9BCE10489966EE882DAB17A33B786AA5F73165A54051300B1DF9280392A3EDE9D3FC9C4D8A6A06351F6EF3598E8DE2B39D3B19AF64A1716CD15826C3F24CB13DEB722C3A03EF1D2BE2D0A5A6E210FF5D018367BE3BF99EA26BA006E5164A4DD55AABCD449DE5CE1864825DC160E50D509EB0E6FE723EF182681EDDB94084B83EC9E2E943E87CB87509AB0FD9B1CA22C1CEAFF39FCACF6729FC0E0578670D87D7F0F9CCBE09CB3E12CEB895572A9979D10BFDBFAFA260568D8DB184BE12B3E3193E07729CE3C1D9CD8283ED6983A06388036A0A70294F23392944778280E7DE9F60163A8150E30FF4A4EA02792CBE8305BAA2E99AFE51E17DAFC56BE0D384147BCD38E9D12934EC712622217773A4B3851A9B0C6C7C3E01F6111A1E1A557F4E2AE4A247CE9B75CCCCB1819825F3054AA1C055BD3E2340093AE2EF1D0FA5A176825EFDF79507027F5104080009142F0D43E2F10CFAD220813BBB9014D4F4325EDAC538FB5E82B753E2AD3B24607D7380AA64FCB98B59EA8B5A736B809383248CECE0B17255EA559E90127F778AF6D7E8A66DAD91
$ od -An -tx1 cipher | tr "\n" " " | sed 's/ //g' | awk '{print "0x"$1}'
0xa14ddfb8cb18cf8b22e898e7ce6a2050b2f732e462b987cd5924605eac67c6d2ce2e95ea688299aec2d3b4b9544d6c30ab6d1f55c8e498b9be30dbb4a8bdd7300aa51cd00812db242c8b58952338f1e37439c74dc063f85c4997c5a7dd99ff4cba4322ba7bcf8c967a5c4d8560dda2607454605339a28cdc0c046e51ac828e6913588509be1e9492af42e01cac6a0301244dcadaebfbe8408120d7136cf3440348095b8996c3a3306c4bb6f0959c821137c64e1d6eb6bbabf60529166b777e6fc02afe0194683622f3420077097d7987786d06f601f9231677340e288828ee9a56e6e57a5f9435468a252765289e56b8ae9eec7189aca04f556eac0af3c30f862440f61bda0fbbd92975c8f83b78b6ad586dc3697955ff92b222b585017f8b58119707c65e222cde343da8f4f058b78d2554fd624a22df567c51fcac5f51498828c775a2a67a5ec0a6e10a3f329d2b3e42cf1666268b174eab14501d89ffaa6943c059f81b00cc29f827ef489f99ccc94cd3b5780924f25c76c85e867df5134d2ea1e45f9c1a6c74b143eb0c051254aede5d0f4e2deca6461f482703b75f0df85542ee25783ffd6ee1dd508c1b7679e17bd2030040a82e7873bb4c5cc83db817f7d7cb776c178f8750f8b5f3c00839cf005e0aadbe6ecfc14c6d603f3feb6c1eaf98b9c902b098867b5505bc14ab3b359f7f6218e6713ae9ed5a1025b8adc415
ps_and_qs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
from crypto_commons.rsa.rsa_commons import gcd, modinv
from Crypto.Util.number import long_to_bytes

e = 65537
pub1 = 0xCFCFBBEEA7DF143A8AC208B1AA1D2F86545AC4CB588C94A3FB1C14AD91A4F0B936157C5A4B869C18A8B864F4726BF8FCDC020CB41042BAC96784AB7D03F9374947EFB0BC3D665831974340159FFC3DB7C8E74B6390FDA6EEC30B81C6FF624E8D3F5B17BFB7A5C7FFD8ECF4E6518B393ABEFDDD0FAEBA4308746BA63F8106B59D7E058943A00131A7D4E538C464B270577647EDBC478CC1CE9585EFE877305B3A7C2E7C44DB5475EDDADC345A2C90A946771CAC0A454CDBCB461F2840E7613C83E9CECC94037FA09BB9DAA3F180562C01DF0BE6C51F0C06E8F0E2D6E1A5E50D0A28C3881140770A9F45934146B7F359B939CE23F0FA507A6F4E454571430952003C20F1D97A67140B6E5FCBFB3B376E4E24969AEB1D489CFC72AF4F15A4788A1AA97C89756D1D4D94AA47E7CD3A81AECB92448CC92C77D2EF576AA0DBC1350862ACCDDADDBCE80357F0CD5B854DD0F8C4627FE4B718B24ECFE11ED24C3BE22F00643BBED4EE5E345AF176E5B76D23A2F80E0EC6F34E5718C62A70FE5570C28B807B44F22EADEBD9B5FF906F6A85BE88C0C8F6E5F880A51F17F84DB1C2EEFEA8AF34040444CED1A37DF0E4F5F72CC3F50B7E427C8C2D8B6186EAD762F0C444B3CA3A0103ED12A93BCE9CAE7479A229EBBC0A648EAA6F97E5051A66EB09EBD7348E92F75F125EBDC367E2A7D1DA7759D41FAE2E2635BF4B7A7F91BECAB3AC7D05BD
pub2 = 0xBB33CC7FCC8ECAF3BF9ED95C583792E1EC6B80EE875EC2064DBCF07595C8344923BF536524D4E0A75574C7798C73B197DD2B1B42054B1E49CB45FBF04E6F114CF8A365C3DF3645524F778268038A3FA26802E9D1EDBFBB5EDFB5A0C375370D7F10F57DABBD4F771DAD3632F01B9BCE10489966EE882DAB17A33B786AA5F73165A54051300B1DF9280392A3EDE9D3FC9C4D8A6A06351F6EF3598E8DE2B39D3B19AF64A1716CD15826C3F24CB13DEB722C3A03EF1D2BE2D0A5A6E210FF5D018367BE3BF99EA26BA006E5164A4DD55AABCD449DE5CE1864825DC160E50D509EB0E6FE723EF182681EDDB94084B83EC9E2E943E87CB87509AB0FD9B1CA22C1CEAFF39FCACF6729FC0E0578670D87D7F0F9CCBE09CB3E12CEB895572A9979D10BFDBFAFA260568D8DB184BE12B3E3193E07729CE3C1D9CD8283ED6983A06388036A0A70294F23392944778280E7DE9F60163A8150E30FF4A4EA02792CBE8305BAA2E99AFE51E17DAFC56BE0D384147BCD38E9D12934EC712622217773A4B3851A9B0C6C7C3E01F6111A1E1A557F4E2AE4A247CE9B75CCCCB1819825F3054AA1C055BD3E2340093AE2EF1D0FA5A176825EFDF79507027F5104080009142F0D43E2F10CFAD220813BBB9014D4F4325EDAC538FB5E82B753E2AD3B24607D7380AA64FCB98B59EA8B5A736B809383248CECE0B17255EA559E90127F778AF6D7E8A66DAD91
cipher = 0xa14ddfb8cb18cf8b22e898e7ce6a2050b2f732e462b987cd5924605eac67c6d2ce2e95ea688299aec2d3b4b9544d6c30ab6d1f55c8e498b9be30dbb4a8bdd7300aa51cd00812db242c8b58952338f1e37439c74dc063f85c4997c5a7dd99ff4cba4322ba7bcf8c967a5c4d8560dda2607454605339a28cdc0c046e51ac828e6913588509be1e9492af42e01cac6a0301244dcadaebfbe8408120d7136cf3440348095b8996c3a3306c4bb6f0959c821137c64e1d6eb6bbabf60529166b777e6fc02afe0194683622f3420077097d7987786d06f601f9231677340e288828ee9a56e6e57a5f9435468a252765289e56b8ae9eec7189aca04f556eac0af3c30f862440f61bda0fbbd92975c8f83b78b6ad586dc3697955ff92b222b585017f8b58119707c65e222cde343da8f4f058b78d2554fd624a22df567c51fcac5f51498828c775a2a67a5ec0a6e10a3f329d2b3e42cf1666268b174eab14501d89ffaa6943c059f81b00cc29f827ef489f99ccc94cd3b5780924f25c76c85e867df5134d2ea1e45f9c1a6c74b143eb0c051254aede5d0f4e2deca6461f482703b75f0df85542ee25783ffd6ee1dd508c1b7679e17bd2030040a82e7873bb4c5cc83db817f7d7cb776c178f8750f8b5f3c00839cf005e0aadbe6ecfc14c6d603f3feb6c1eaf98b9c902b098867b5505bc14ab3b359f7f6218e6713ae9ed5a1025b8adc415

p = gcd(pub1, pub2)
q = pub1 / p
d = modinv(e, (p-1)*(q-1))
b = pow(cipher, d, pub1)
print long_to_bytes(b)
1
2
3
4
5
6
7
8
9
$ python ps_and_qs.py
�H4؋ѝ2l�r
�puF`u�܎��3�4CT�R
  ��V�.dZ[]���%��)() _�d�
                         |�o�h�o�V��s{t_�vӫ�1ۧ�[:�X�Y��%�%��r�9dJ�|�������7��M��
                                                                               g�B����݁t^Scq�`H�0�c�f��Ŏ\�
                                                                                                         6�a ��"5`�_�et:
��a�C	=�L�X�	UmL�b�'���\�X��3��l>��(W!��T����e�DǷ.��?f�L.�U������nR~J�.�'�&/��w����!A�wS"U��Z�*�	���E�T�d�w�@�J!�=��"��,����Dh������	����(�l���4UayXg4Ї4Z�Z��Ma��5���|�ۻ�;Z�-S�@��]>	\n6>�g�MBK��E�@�a�VYԹB�p���`[�5�1�],�GA".�
                                  ��5�摨SECCON{1234567890ABCDEF}