Worksheet 03: Cryptography II

Worksheets are self-guided activities that reinforce lectures. They are not graded for accuracy, only for completion. Worksheets are due by the start of the next lecture via Blackboard link as a single pdf document. Be sure to properly label each question.

Questions

1. What is the key difference between symmetric encryption and asymmetric encryption, and why is asymmetric encryption vital to public-key encryption/decryption.

   Reveal Solution

   In symmetric encryption, the same key is used for encryption and decryption routines. In asymmetric encryption, the key used to encrypt differs from the key that used to decrypt. This can be used to enable public key encryption because you can distribute a key, publicly, that anyone can use to encrypt data whose resulting cipher text cannot be decrypted by that public key. Instead, it can only be decrypted by another key, kept private.

2. What is hybrid encryption and why is it useful?

   Reveal Solution

   Hybrid encryption is when the encryption scheme mixes symmetric and asymmetric encryption. For example, the public key portion is used to exchange information to establish a symmetric key used for future encryption. The reason that this is useful is that symmetric encryption/decryption is typically much faster to perform than public key based encryption. For streaming protocols, like HTTPS/SSL, this is vital for performance.

3. In the book, read the Math details of RSA Public-Key Encryption, page 38 (section 2.3), and then complete the first exercise on page 39. Specifically, in the toy example, does \(e=5\) satisfy the rules?

   Reveal Solution

   From the example, \(p=5\), \(q=7\) \(n=pq=35\) and \(\phi(n)=(p-1)(q-1)=(4)(6)=24\) To check if \(e=5\) satisfies the rule, it must be the case that \(ed = 1 + x\cdot\phi(n)\) where we can choose \(x\) and \(d\).

   If \(e=5\) would satisfy the rule because we can choose \(d=5\) and \(x=1\) then \(5 \cdot 5 = 25 = 1 + 1 \cdot 24\).

   However, it is not the case that $d$ must be 5. In fact it can be the case that $5d$ is any number on more than a multiple of 24. Note that \(24 \cdot 4 = 96\) then if \(d=19\) and \(de=95\). So in this case, with \(e=5\) we can choose \(d=19\) and have a valid RSA key pairs of the following

   • \(d_A = (19,35)\)
   • \(e_A = (5,35)\)

4. Decrypt the number 10, by hand, using the RSA private key pair (5,35) (like in the example above).

   Hint: Note that math under the modulo allows the following \((a \cdot b) \mod n \ = \ [(a \mod n)(b \mod n)] \mod n\) which is very useful for doing large calculations by hand.

   Reveal Solution

   We need to compute $10^5 \mod 35$. To do this quickly, we can take advantage of modulo rules that allow us to distribute the mod within the multiplication. For example,

   \[10^5 \mod 35 = [(10^2 \mod 35)(10^2 \mod 35)(10 \mod 35)] \mod 35\]

   \(10^2 \mod 35\) is simply \(100 \mod 35\), or 30 as \(2 \cdot 35 = 70\) leaving a remainder of 30. Rewriting above, we get the following after iterating using this trick

   \(\begin{eqnarray} 10^5 \mod 35 &=& [(10^2 \mod 35)(10^2 \mod 35)(10 \mod 35)] \mod 35\\ &=& [(100 \mod 35)(100 \mod 35)(10 \mod 35)] \mod 35\\ &=& [(30)(30)(10)] \mod 35\\ &=& [(9 \cdot 10^2 \cdot 10)] \mod 35\\ &=& [(9 \cdot (10^2 \mod 35)\cdot 10)] \mod 35\\ &=& [(9 \cdot 30 \cdot 10)] \mod 35\\ &=& [27 \cdot (10^2 \mod 35)] \mod 35\\ &=& (27 \cdot 30) \mod 35\\ &=& (27\cdot 3 \cdot 10] \mod 35\\ &=& [(81 \mod 35) \cdot 10] \mod 35\\ &=& (11 \cdot 10) \mod 35\\ &=& 110 \mod 35\\ \end{eqnarray}\)
   Note that \(35\cdot 3= 105\) so \(110 \mod 35 = 5\) which is our answer.

5. What three properties do digital signatures provide?

   Reveal Solution

   1. Data origin authentication
   2. Data integrity
   3. Non-repudiation

6. In RSA (and other asymmetric schemes), the usage of the public and private key are inverse operations of each other. That is, in the traditional usage, encrypting with the public key can only be inverted (or decrypted) with the private key. But the same is true in the reverse, items encrypted with the private key can only be inverted by decryption with the public key.

   Come up with a system that provide secure encryption with a digital signature for two communicating parties A and B with secret/private key pairs \((s_A,p_A)\) and \((s_B,p_B)\), where \(p_B\) and \(p_A\) are known and verified by A and B.

   Reveal Solution

   Assuming A wants to send a message \(m\) to B, let’s define a tag, or signature as \(t=E(s_A, m)\). That is, the tag is the message encrypted with the secret/private key. Finally, A sends cipherext \(c\) of the tag appended to the message all encrypted with B’s public key: \(c=E(p_B, m \circ t)\), where \(\circ\) indicates append.

   B can then decrypted the message with their secret key producing \(m \circ t\). Splitting the message and the tag apart, B can further produce the message again by decrypting the tag with A’s public key.

   If the two messages match, B knows that it must have been A that originated the message as A is the only party in possession of their secret key, which also provides non-repudiation (assuming sole ownership of secret key by A). Additionally, there is data integrity – the message hasn’t been altered otherwise the two messages wouldn’t have matched.

   Note that his scheme is pretty inefficient as it requires sending twice the data for every message.

7. Assume you have a cryptographic hash function \(H\) that you can use in the scheme for message secrecy and signatures using RSA. Can you improve on your solution?

   Reveal Solution

   Yes. Instead of the tag being the \(t=E(s_A,m)\) we can instead encrypt a hash of the message \(t=E(s_A,H(m))\). Like before, the ciphertext sent to B is the encryption of the message with the tag appended.

   When B receives the message, they again decrypt it with their private key and decompose the message from the tag. To retrieve the digest, B decrypts the tag using A’s public key. To verify the signature/digest, B only needs to hash the plain text message and check if the digest matches.

   This improves the scheme before because the tag (signature) is of a fixed size, rather than the size of the message.

8. Which property of a cryptographic hash function is that, given an input \(m_1\) and its \(h_1=H(m_1)\) it is infeasible to find an \(m_2\) such that \(H(m_2) = H(m_1)\).

   Reveal Solution

   This is second-preimage resistance. Note that this is different from collision resistance because you are assigned a message you must match to, as opposed to having free choice of finding two distinct messages that match.

9. What is the difference between using a general purpose cryptographic hash function and a MAC?

   Reveal Solution

   A MAC, unlike a general purpose cryptographic hash function, is keyed. The key should only be known to the originator and any party they share it with to verify the MAC. A cryptographic hash function can only produce digests for its input and is not necessarily keyed.

10. MACs provided data integrity and message originator security, but not non-repudiation. Explain why not?

    Reveal Solution

    There is no process that would prevent someone to deny (falsely) that they did not originate a MAC as it is impossible for a third party, just using the MAC and the key to show it must have originated with a given entity.

11. Compute the final key in Diffie-Hellman \(p=13\) and \(g=3\) if A chooses \(a=4\) and B chooses \(b=6\). Do it by hand.

    Reveal Solution

    A computes \((3^4 \mod 13) = (81 \mod 13) = 3\) and sends 3 to B.

    B computes \((3^6 \mod 13) = [9 \cdot (81 \mod 13)] \mod 13 = (9 \cdot 3) \mod 13 = 1\) and sends 1 to A.

    A then computes:

    \[\begin{eqnarray} {(1)}^3 \mod 13 &=& 1\\ \end{eqnarray}\]

    B then computes

    \[\begin{eqnarray} {(6)}^{3} \mod 13 &=& (6 \cdot 6^2) \mod 13 \\ &=& [3 \cdot (36 \mod 13) ] \mod 13 \\ &=& (3 \cdot 10 ) \mod 13 \\ &=& (30 ) \mod 13 \\ &=& 1\\ \end{eqnarray}\]

    The shared key is 1.

12. Download this zip file that contains the starter code for this project. Unzip it, and then open the directory in a new VSCode window. You should be prompted to open the folder in a container, say yes!

    If you haven’t completed Worksheet 02 Q12 please do so first so you can test your C# environment.

    Once the container is open, you should open a terminal window. You can do that from the menu bar, or by using the shortcut Ctrl-` (backtick).

    Then in the terminal dotnet run to run Program.cs – which is just a hello-world program. If you’re prompted to install the C# framework, you should select yes to that too.

    Your task is to edit Program.cs to be able to decrypt a hybrid encrypted message from Bob to Alice (you are Alice in this example) and verify the authenticity and integrity of the message.

    Here are the PEM encoded public and private keys for Alice (remember, you are Alice).

    -----BEGIN RSA PRIVATE KEY-----
    MIIEowIBAAKCAQEAneV0ccSYMbjk+mkI5s+d/ZuhGPFa87T9glRv+QVoKShtoSD9
    P6vHrOOORnfvdHVkWZDhWiKMfZpp43ogAmLJCB8XDr4W+ymUANrcYMqys2dX6D3B
    3kVTX1hbTP9s7Ou1JUODcSLfQh8j8LxZqA/LkRqv31Ji4fN4DL8kDmopMSFS+o9/
    zZIPiOEblbsADyV5tYf+yDDLMoJuv7gU3eZpBvmFtuAycUHpnQOuVlrf6Ea0PBR0
    pUdbJOOqmXUo0yCVApuV+/Gz7PbSQkVaogQ0+FzuyKx9dRckLoy+k0A0o+OyAk/T
    +zeSk87DWNDubR9QGF2cbqMVH8syxsqo7wogLwIDAQABAoIBAAGdq3AbBnTpaWWx
    dUop0S1n9KFoN7mRxLYBcWnqs7+w4bpWt5csuPm2FHeR9HN/j6jY/wcCOBtBXTJB
    ec1i2Tk9J2ontapMj4hL6E1EFcl/PI35MwaezmhSsHbpXRVQB9KoGuxcyOZVokA6
    KG+I+QwOailbbJaj/FQ8RCN/oG9K92I1PIlo3l+xoBTqX/+9FyLodhz7bhk6uXf6
    QHZ9DnzpAz+YENuIIEs8xOiAtukaIfQvH28b/oyzJiRz3JlhaRr09dKjLRQm56T9
    5oJ+/NbQ1NOIajvb5D7mdKZCHa+3txR80C65ds+trtiV9oNtATXG+02VBOAXyEA9
    Qb2obWkCgYEA2vxlb9qnVpE3yw6Uf/eBTXSw+Gx217EzqhHodejJ/+s6BnHjEE4X
    jElVHW3W+Xf7Av4XHjhl+ePwYQuuK9+iOtRyMMxm2c6oZfaCpPuXNsgFv3ipv2rB
    Xs5Jy8EZlswv/N/5r8wEC52p+wPVr7zVifBo0yowl/NbSAJ/y/uE2QkCgYEAuJWw
    GFQX4gN0uhaHrFz/orFJcpbVcLcUQX21zZ9zwBu/b8Uxe00emUQpQyFg5N4NrzZ6
    rY2UmXDaYo3QW6HsK4zVi6k50Bt889XqXdzRU3UOYV2o1CZ0uW6mlso5kc5257UF
    2FP6fSyJbNB+PdCmDZ2O66Ik1MRdxR+0VPL/lXcCgYBMz/OUxJGl39I+O6MDMAH+
    9UuOGB2nktSYdyefFESmrA/yashG092Wq7JbXEfnwZoedpoNU6MRgE60+6/gW9U/
    5X0YeNoq1D5lZY516HomEQtTGjQQnJWvd5STD+y15HGAtd+TNnDE0kzpa3Ls7cPJ
    WraqO0ZIRmhiXd4N4u+6YQKBgQCfSLzfIaJCbU0LUGnfuZj34hlJgxPI4pPeOAbs
    3A5c1xUJ9JbQmiovhHw+68zbcytH6bFPlv+GsbYimdIVYNOWeT/F91BmX3IiUJSg
    Tu9sH3U7XEFWYaEUa4HiWbv4MLy3EqVqmn1sC0TD2980pJrG4RH2EMPLv3BTrRpG
    vDMF3QKBgHatS/ELwoTf/PEQo1tL4tepgUo3itFQndtZ2ZwWcjrcMGE+0wgmDIiB
    1TwwPL3yRRu66e4gDJh3A9SJmdKYv8Em0KWSRnWyACZi1Ba4xl7sINVhBT9CzI57
    TwCd81NHMVYndgJm2iaOUP3Rv2Zao6IkuPGyxxlo8eh4hJBOv9mY
    -----END RSA PRIVATE KEY-----
    

    -----BEGIN RSA PUBLIC KEY-----
    MIIBCgKCAQEAneV0ccSYMbjk+mkI5s+d/ZuhGPFa87T9glRv+QVoKShtoSD9P6vH
    rOOORnfvdHVkWZDhWiKMfZpp43ogAmLJCB8XDr4W+ymUANrcYMqys2dX6D3B3kVT
    X1hbTP9s7Ou1JUODcSLfQh8j8LxZqA/LkRqv31Ji4fN4DL8kDmopMSFS+o9/zZIP
    iOEblbsADyV5tYf+yDDLMoJuv7gU3eZpBvmFtuAycUHpnQOuVlrf6Ea0PBR0pUdb
    JOOqmXUo0yCVApuV+/Gz7PbSQkVaogQ0+FzuyKx9dRckLoy+k0A0o+OyAk/T+zeS
    k87DWNDubR9QGF2cbqMVH8syxsqo7wogLwIDAQAB
    -----END RSA PUBLIC KEY-----
    

    And here’s Bob’s public key

    -----BEGIN RSA PUBLIC KEY-----
    MIIBCgKCAQEAvvJruGVVmQUcljfoYisf8oOkS2MWpdo6ZiK5YyCA3umfL7iphUuP
    vvueEp59rEHm5bp4AeltsPuH2sbLeIi4CjhhlWi5S6MPjej0uM+/SklIlLFLNJO+
    ctblcRyFLp5tW2HGbcfa1EkGf/hS8IFNwYm4X05bgXZjnOFcW5gBcliEtTBwMdA2
    wH5o958oqJmf/K2tTsC3p8kKm8UTa6pWZoEE3kVsLA/r9D/ZSkSlLrOA3xPMZjx5
    nKrXhgZYuZKK8R4m37aoygYCiB42MaxlEgVCD/jy9HwJW2Zczl6YOJ/ynJQ0QMh1
    Gzi18SDuaJU25wyhE+qCWyNK7mVBr1HbawIDAQAB
    -----END RSA PUBLIC KEY-----
    

    You receive from Bob the following three items as hex strings, decrypt it and verify its authenticity and integrity. Provide the decrypted message and the line of code you used to check the signature.

    The encrypted message (using AES-CBC mode with PKCS7 padding) (be sure to scroll all the way to the RIGHT!)

    ABB6ED6446AA0B28077D7CD6D198F8A2092E1065A48EAED8782172D9E67869B30F8303F9669A5B6A905A2D8491FBFEC0BF82EA7AD479322D07F8A221B7A1DC510555F4624E4C165FE32B220DB6E74ABAB9AFA2D432847B6FF41048608AA84064062901C072C40DC051DF75053C4A89719D2EF3310D88AFF1248CA0D3AB7EF83C33ED02F5EECA416053D7862A01CD589E08781A16984D93C9A2CDE25046FA191EFC88F75B5442AA3F4BF958D2951D3D67D5875A52C0AD989340A52394837CFB8E02FE57C7B80C6B5D1B075DB56B9F8C4750DAE69FEDD8C81F0F301FD12A869402FA21CAA5FC3582DC2293BF59128F8630166454E2E408329D2AE96134388B3714D089AD2F6B00DFF5198141E02D698C330E3A99E9BE152A2720ECC9F6D0200CAAB845C95564D07097D731CE26C8F3664248E73E28AFCCBE4B6224E542181A7A4829CE7C993B81D5536535560B3CFAA0DD61FD9CB656BA4ABC7FCFB4DD9B005153E61A295AD8BADBAD15A5139E28A121EEDAF40B25DEA6DDD484A94BD32CAB037B7C58BF31E2E4302765C126DE8AA458E3D025F04C0A7D50ED804F3EEB3792A4E2667270CF9F00A5C84A5A41AE33DF5D6037BDC7BE59B1D2FF539DE941BCF7246CB3499A4F1C77A655805C469812E4A3A2E2CA7B7F2F9E7BE6584764F1B03F74682B1B1A06DED8098CA3D360162162D410D8E18438D74AF8DFEF14A5CCD22DA75A7B670C8DC4FD6842A526F2FE94FB8C0B216F7DE349969139838E1E29836E574904F1D485198E7A982F4D6C5122381BDD3F89F04B37E82E1EAA179723E58651933B4E9FE0A7B11E89E09B45E90241C6B9D404B0A8BE0E92A833B7547BDF2DE10970DF1745C4352E9C9067B1B9D0B244241D79F44CBAA4AA33FB88962BDBCAE3C0053C667F467E3DAE5D152A0F7E1F63A01B25AD380C2969EEBDAE820EC280455C91BAC109587210DF7698BFE1AAF9C467FA159D51042580A32ACDF20A82DD00AF45953FE9E92F0B5CD5B9CC3EEC250DBC717E30AECEA9F625ED2238DCF2BB3A5DF5E0A2C84BD833A5CDCCE71B1E59996F4BFEE5E50044A55C414E74936CE931F00559AA64050193FD92C4265E180B418F314989AFE81BA77DCAFA41A4670CBB3EBF79E72D491E5D1A652797179169DD2A0B6F2C931EEAA0A7F4B364688299F13DC17F393DFB29E6EE03CF046CCDD679EB740CF4A4DA651514E8665E7208A66C23B2845DDC29130F598AD0B692D7045F0E91C275D5318EB9A6550F55414318F7E57D468371CD74EC27C5144CDB226FFEC84AF67E7866F2371E2C7E265E61731ADFFFC99CE6D94E385FDDC94DCE8393BE0B183CA0C2F365AE96C7EF00394F97FE83FDEB3B22762978E58C624224AA53D8D713C0B51EE9D67E3820A19FEFD81EC6A00808CB2167EA0E50F26B4924ED1D4190563F1CD2BE82CC44B49BD1E98B261775A5F9E619DD6C108607EA5F2E6E16E3272DD289193263FCBAA045CAAE0F061CD3810B9B01F162FC99D68578927BBBFB9C13C47F1113A8A32954822BAC301C9DE5CDE2636EFAC3BF434AF25508F7FAB49D154CDD8AC3C9E78D6A8CBEE2D8F4A312C0A39AF89FD6AFF572090F7EC4AF4E1366C40FFEFCFA5FE28CD96384B04F868F351E060D041B09FE908D5032041F472B028AF973EFE4816D8FB1D8AB69B3C622B3E472B790D3852DD5CD306FD4A5DEE536E93746C1C89F35C941E6BC75DC58CFA286F982B42EB85C27BA6E611ABE7D401DDD44595F2C1381BCD589F04DB9B6222B206C4FA24B428913684F491ADD96019395ADC1A8E8CA7198B04DC5CB5494D2343C331B326DAC084B4F81CB57BC24AF916412A70159B5E53CF54C6BE9A812FB83353917463F1CB9D87244CB8D4B2D2B4594CE1B647F4B264EA1FC0A48BB233DDB183FD89D07D5717BA4332BDBA44288095911533543EF68705378E2D259E913F9860370D4752FEA6D07BB137A531A8AC3B568B8E0B5FA83E18FC62A17B47B3B64521A811BAC2F730BBB7EF9F803946280CD26ED92EFA7FE10D84935946F275CCE6743A37CE5A85A0FAFE0FD660DAF7181DF4427E0E0BAD932FB2E0D619F8629A012AC22C7EDDEBA5BC7E1D0DEC1CD33
    

    An RSA encrypted message that contains 32 bytes of the AES key and 16 bytes of the IV. The RSA encryption uses OaepSHA256 padding.

    325FAAB4CBC7F43DE9ADA7FE9613F6E3714EC63A80D1CC91B8ED1AB70E1C529F797FD648877C50E83E6B42983C1D0B50F4F6D17484577F68391FBBF3A70DDAAD82DA62F779FDA8D3A57EB7221EFC69E4DFA3F6B1861FD30E8F33BDA64D4C846D09B7A1C9C60154427BD061FD07BD7C05E50DC9F71B966EF044A2C6E20ACF32D0C09A7F59FFB831C7E4FC179F12F89776281B0BBC4BDDE188E5AEEB56E7778FFDCE2BE4F38F899CF034EF472D030EAFECD2A93EF15B64B437B7C9E76D53C648C626E5F0A48C9F3ECD021049EEA962A08D18F534C4847BF58B2157EFE9EDD5E31D70481EDD9F3A003A52A0D7D45DA051DD8AA8B15C945A2802E7CC5522C64237B5
    

    And an RSA signature of the unencrypted data of the message using SHA256 and PSS padding.

    983580498196F90C9F82A40D17C6FCE78921299AAA1A9EBED1E89FAB2E70FFA79A3352548411C637107194C887439305F2921D726BCB1F9F8AFD86920D4CFAA4D8578372BF34AECDCC3C83D90E443ED3CF7F186EEB911C04F8719B6C70969B251CB10872BA1EC9F233E7F2A94FC25F2AF3DE26AA7708BAE388F4FAB6B3A5820B8C733ADD761755AD3D9B9774C72AF44C9B0430D5B732F5E9FE55C786E29E49506EA5C0C6D56CBD4259E60335FB308F7606071EEE1EA85A372EF047BC8B00B36782E466FD03120E287F387FF270685B470B298116C9DA9065D922D80AE0219531DAAFC45BE3765811FD14F3E2AB32FF160167A389608F01C6B66081B90379B3FA
    

    Tip 1: Recall from Worksheet 02 Q12 that to convert to byte[] from a hextstring you use Convert.FromHexString and to convert a byte[] to an ASCII string use Encoding.ASCII.GetString()

    Tip 2: The System.Security.Cryptography library and it’s documentation is what you need for this.

    Tip 3: When loading RSA keys, use ImportFromPem() you can either only load a public key or a private key, but if you load a private key, you must load it after loading the public key.

    Reveal Solution

    The message

    ”””
    Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.

    Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this.

    But, in a larger sense, we can not dedicate – we can not consecrate – we can not hallow – this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us – that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion – that we here highly resolve that these dead shall not have died in vain – that this nation, under God, shall have a new birth of freedom – and that government of the people, by the people, for the people, shall not perish from the earth.
    “””

    rsaBob.VerifyData(plain, Convert.FromHexString(signature), HashAlgorithmName.SHA256, RSASignaturePadding.Pss)