{"id":1443,"date":"2010-12-15T12:45:51","date_gmt":"2010-12-15T16:45:51","guid":{"rendered":"http:\/\/www.acarlstein.com\/?p=1443"},"modified":"2010-12-15T15:23:51","modified_gmt":"2010-12-15T19:23:51","slug":"introduction-to-network-security-%e2%80%93-part-10","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=1443","title":{"rendered":"Introduction to Network Security \u2013 Part 10"},"content":{"rendered":"

NOTIFICATION:<\/strong> <\/strong>These examples are provided for educational purposes. The use of this code and\/or information is under your own responsibility and risk. The information and\/or code is given \u2018as is\u2019. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and\/or leave a comment.<\/p>\n

RSA Algorithm
\n<\/strong><\/p>\n

RSA is an algorithm for public-key cryptography. The signals R.S.A.<\/span> come from the last name of Ron R<\/span>ivest, Adi S<\/span>hamir, and Leonard A<\/span>dleman who where the first to describe this algorithm. This algorithm is famous for being the first suitable algorithm for signing as well as encryption.<\/p>\n

RSA algorithm allow to choose which key should be use for encryption and decryption.<\/p>\n

    \n
  1. Public key for encryption, private key for decryption or,<\/li>\n
  2. Private key for encryption, public key for decryption.<\/li>\n<\/ol>\n

    Generate the Pair Key (Public and Private Key)
    \n<\/span><\/p>\n

      \n
    1. Choose two random prime numbers p<\/em> and q<\/em>.
      \np<\/em> = 17
      \nq<\/em> = 11 <\/span>
      \nFor better security, you can use the Primality Test to obtain to obtain these two random prime number. They should be of similar bit-length.<\/li>\n
    2. Compute n = p*q<\/em> in which n is the modulus used for both the private and public keys.
      \nn = p * q<\/em> = 17 * 11 = 187<\/span><\/li>\n
    3. Compute Euler Totient Function \u00f8(n)
      \n\u00f8(n) = <\/em>\u00f8(187)<\/em> = (p – 1) * (q – 1)<\/em> = 16 * 10 = 160<\/span><\/li>\n
    4. Select a public key exponent e<\/em> number where 1 < e<\/em> < \u00f8(n)<\/em> and gcd(e, \u00f8(n)<\/em>) = 1
      \nIf we choose e<\/em> = 7<\/span> then gcd(e, \u00f8(n)<\/em>) = gcd<\/em>(7, 160) = 1<\/span><\/li>\n
    5. Determine the multiplicative inverse d:
      \n\"\"<\/a><\/p>\n
        \n
      1. d must be less than \u00f8(n): d < 160<\/span><\/em><\/li>\n
      2. if d * e mod \u00f8(n)<\/em> = d<\/em> * 7 mod \u00f8(187)<\/em> = d * 7 mod<\/em> 160 = 1 then<\/li>\n
      3. let d = 23<\/span> in this way d * e = 23 * 7 = 161 = (160 + 1)<\/em><\/span>
        \nd * 7 mod 160 = 23 * 7 mod 160 = 1<\/span><\/em><\/li>\n<\/ol>\n<\/li>\n
      4. The public key will be:
        \nPU = {e, n} = {7, 187}<\/span><\/em><\/li>\n
      5. The private key will be:
        \nPR = {d, n} = {23, 187}<\/span><\/em><\/li>\n<\/ol>\n

        Encryption<\/span><\/p>\n

          \n
        1. Sender must obtain the public key PU = {e, n} <\/em>to the recipient, where PU<\/em> is the public key, n<\/em> for modulus, and e<\/em> for public exponent (also known as public encryption).
          \nPU = {e, n} = {7, 187}<\/em><\/span><\/li>\n
        2. The message M<\/em> (also known as the plaintext) must be turn into an integer m<\/em> by using a padding scheme (an reversible protocol) in which 0 < m < n.
          \n<\/em>Lets assume the message is m = 88<\/span> where 0 < m < n so <\/em>0 < 88 < 187<\/span>.<\/em>
          \n<\/em><\/li>\n
        3. Then the sender must compute the ciphertext.
          \n          \"\"<\/a>
          \nWhere c<\/em> is the ciphertext, m<\/em> is the integer message , e<\/em> is the public exponent, and n<\/em> i for modulus.
          \n          \"\"<\/a><\/li>\n<\/ol>\n

          Decryption<\/span><\/p>\n

            \n
          1. The recipient must use the private key to decrypt the ciphertext PR = {d, n} <\/em><\/span>where PR<\/em> is the private key, d<\/em> is the private key exponent, n<\/em> for modulus.
            \nPR = {d, n} = {23, 187}<\/em><\/span><\/li>\n
          2. Compute the message.
            \n            \"\"<\/a>
            \nWhere m<\/em> is the integer message, c<\/em> is the ciphertext, n<\/em> for modulus.
            \n            \"\"<\/a><\/li>\n
          3. Then turn back the original message M by using\u00a0 integer message m<\/em> with the reverse padding scheme.<\/li>\n<\/ol>\n

            Encryption \/ Decryption Example<\/span><\/p>\n

            \"\"<\/a><\/p>\n

            Algorithm Requirements<\/span><\/p>\n

              \n
            1. \"\"<\/a><\/li>\n
            2. There should be able to find values for e, d, and n so for all values of m where 0 < M < n
              \n              \"\"<\/a><\/li>\n
            3. \"\"<\/a> and \"\"<\/a> should be easy to calculate for all valus of m where 0 < m < n.<\/li>\n
            4. It should be very hard for an attacker to determine d<\/em> given e<\/em> and n<\/em><\/li>\n<\/ol>\n

              Possible Attacks to RSA<\/span><\/p>\n

                \n
              1. Brute Attack<\/li>\n
              2. Mathematical attacks\n
                  \n
                1. Determine d<\/em> directly<\/li>\n
                2. Determine the Euler Totient Function \u00f8(n)<\/em> without using the prime numbers p<\/em> and q<\/em><\/li>\n
                3. Factorising n<\/em> into the correct prime factors p<\/em> and q<\/em><\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

                  Key Distribution<\/strong><\/p>\n

                  One of the important aspects is how to distribute the keys between the sender and the receiver. For example, one way is to use the public-key encryption to distribute the keys.<\/p>\n

                  For doing that there are three different methods of distributions that can be used:<\/p>\n

                    \n
                  1. Public announcement,<\/li>\n
                  2. Public-key authority, and<\/li>\n
                  3. Public-key certificates<\/li>\n<\/ol>\n

                    Public Annoucement<\/strong><\/p>\n

                    One way to distribute the public keys is having the sender to distribute the public key to the recipient; however, this have the disadvantage that an attacker could create a key claiming to be the sender. This disadvantage is known as forgery.<\/p>\n

                    A solution is to create a public-key autority.<\/p>\n

                    Public Key Authority<\/span><\/p>\n

                    A public key authority is a central authority that maintain a dynamic directory of public keys for all the users. Example: {name, public-key}<\/p>\n

                      \n
                    1. In a secure way (in person), each user register a public key in this directory authority.<\/li>\n
                    2. It is required that the user known the public key for the directory.<\/li>\n
                    3. Only the authority known the corresponding private key<\/li>\n
                    4. Users interact with the directory in order to obtain the public key securely<\/li>\n<\/ol>\n

                      Steps:<\/span><\/p>\n

                        \n
                      1. User A send\u00a0 a timestamped message to the public key authority.
                        \nThis message contain a request for the public key of user B.<\/li>\n
                      2. The public-key authority responds to user A returning an encrypted message using it’s private key. This message contains:\n
                          \n
                        1. The original request so it can be use to match with the request<\/li>\n
                        2. The original timestamp so it can be determined if the message is not from the public-key authority.<\/li>\n
                        3. The public key of user B.<\/li>\n<\/ol>\n<\/li>\n
                        4. User A store the public-key of user B and use this public-key to encrypt a message that will contain the identity of user A plus a “nonce N1”. This message will be deliver to user B.<\/li>\n
                        5. User B send\u00a0 a timestamped message to the public key authority.
                          \nThis message contain a request for the public key of user A.<\/li>\n
                        6. The public-key authority responds to user B returning an encrypted message using it’s private key. This message contains:\n
                            \n
                          1. The original request so it can be use to match with the request<\/li>\n
                          2. The original timestamp so it can be determined if the message is not from the public-key authority.<\/li>\n
                          3. The public key of user A.<\/li>\n<\/ol>\n<\/li>\n
                          4. User B encrypt a message using the public-key of user A and send this encrypted message to user A.
                            \nThis encrypted message have:<\/p>\n
                              \n
                            1. User A’s nonce<\/li>\n
                            2. A nonce genereated by User B<\/li>\n<\/ol>\n<\/li>\n
                            3. User A encrypt a message using the public-key of User B and send this encrypted message to user B.
                              \nThis encrypted message holds:<\/p>\n
                                \n
                              1. the\u00a0 nonce N2 of user A<\/li>\n<\/ol>\n

                                (This will ensure user B that the encrypted message is coming from user A).<\/li>\n<\/ol>\n

                                \"\"<\/a><\/p>\n

                                Disavantages:<\/span><\/p>\n

                                Since the users must appeal to the public-key authority in order to obtain the other users’ public key it can produce a bottleneck.<\/p>\n

                                Public Key Certificates<\/strong><\/p>\n

                                Another way to exchange keys without the need of a public-key authority is the public-key certificates. The general idea would be:<\/p>\n

                                  \n
                                1. A certificate is a data block that contains a public key plus an identifier of the key’s owner. This data block would be signed by a trusted third party which would be the certificate authority.<\/li>\n
                                2. A user would generate a pair key and send the public key to this certify authority in a secure way and obtain a certificate issued by the certify authority (the trusted third party).<\/li>\n
                                3. This user then would publish this certificate so another user can verify that the certificate was created by the trusted third party.<\/li>\n<\/ol>\n

                                  Please notice that the certificate authority (the trusted third party) is the only one that can create and update certificates.<\/p>\n

                                  Steps:<\/span><\/p>\n

                                    \n
                                  1. User A supply a public key PUa<\/em><\/span> with a request for a certificate to the certificate authority. This request must be done in a secure ways such as in person for example.<\/li>\n
                                  2. The certificate authority would provide user A with this from:
                                    \n                                    \"\"<\/a> where E<\/em><\/span> is the encryption algorithm, PRauth<\/em><\/span> is the authority’s private key and Time1<\/span><\/em> is a timestamp, and IDa<\/span><\/em> is the user A identification.<\/li>\n
                                  3. User A then can pass the certificate CA any user (in this case user B).<\/li>\n
                                  4. User B get the certificate from user A and verify if the certificate correspond to the certify authority by decrypting the message using the authority’s public key:
                                    \n                                    \"\"<\/a>
                                    \nIn this way it can verify that the certificate is not counterfeit.<\/li>\n<\/ol>\n

                                    \"\"<\/a><\/p>\n\n