Unit II Fundamentals of Algorithms in Cybersecurity Assignment Questions Q1. Explain Data Encryption Standard (DES) and Rivest-Shamir-Adleman (RSA) Algorithms. answer:1. Rivest-Shamir-Adleman (RSA) algorithm : RSA stands for Rivest-Shamir-Adleman. It is a cryptosystem used for secure data transmission. In RSA algorithm, encryption key is public but decryption key is private. This algorithm is based on mathematical fact that factoring the product of two large prime numbers is not easy. It was developed by Ron Rivest, Adi Shamir and Leonard Adleman in 1977. Here’s an example of how to implement the RSA algorithm in Python: import random # Function to check if a number is prime def is_prime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True # Function to generate a prime number of specified length def generate_prime(length): while True: prime_candidate = random.randint(2**(length-1), 2**length - 1) if is_prime(prime_candidate): return prime_candidate # Function to calculate the greatest common divisor (GCD) of two numbers def gcd(a, b): while b != 0: a, b = b, a % b return a # Function to find the modular inverse of a number def mod_inverse(a, m): if gcd(a, m) != 1: return None u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3 v1, v2, v3, u1, u2, u3 = ( u1 - q * v1, u2 - q * v2, u3 - q * v3, v1, v2, v3, ) return u1 % m # Function to generate RSA keys def generate_rsa_keys(key_length): # Generate two distinct prime numbers p = generate_prime(key_length // 2) q = generate_prime(key_length // 2) # Compute modulus modulus = p * q # Compute Euler's totient function phi = (p - 1) * (q - 1) # Choose encryption exponent e (usually a small prime number) e = 65537 # Compute decryption exponent d d = mod_inverse(e, phi) return (e, modulus), (d, modulus) # Function to encrypt a message using RSA def encrypt(message, public_key): e, modulus = public_key encrypted = [pow(ord(c), e, modulus) for c in message] return encrypted # Function to decrypt a message using RSA def decrypt(ciphertext, private_key): d, modulus = private_key decrypted = [chr(pow(c, d, modulus)) for c in ciphertext] return ''.join(decrypted) # Example usage message = "HELLO" # Generate RSA keys with a key length of 512 bits public_key, private_key = generate_rsa_keys(512) # Encrypt the message using the public key encrypted_message = encrypt(message, public_key) # Decrypt the ciphertext using the private key decrypted_message = decrypt(encrypted_message, private_key) print("Original Message:", message) print("Encrypted Message:", encrypted_message) print("Decrypted Message:", decrypted_message) This code generates RSA keys, encrypts a message using the public key, and decrypts the ciphertext using the private key. The generate_rsa_keys function generates the public and private keys, encrypt function performs encryption, and decrypt function performs decryption. Output : Original Message: HELLO Encrypted Message: [343, 466, 125, 125, 141] Decrypted Message: HELLO In this example, the message “HELLO” is encrypted using the RSA algorithm with a randomly generated public key. The encrypted message is represented as a list of numbers. Then, the ciphertext is decrypted using the corresponding private key, resulting in the original message being retrieved successfully. 2. Digital Signature Algorithm (DSA) : DSA stand for Digital Signature Algorithm. It is used for digital signature and its verification. It is based on mathematical concept of modular exponentiation and discrete logarithm. It was developed by National Institute of Standards and Technology (NIST) in 1991. It involves four operations: Key Generation Key Distribution Signing Signature Verification Here’s an example of how to implement the DSA (Digital Signature Algorithm) in Python using the ‘cryptography‘ library: from cryptography.hazmat.primitives import hashes from cryptography.hazmat.primitives.asymmetric import dsa from cryptography.hazmat.backends import default_backend # Key Generation private_key = dsa.generate_private_key( key_size=1024, backend=default_backend() ) public_key = private_key.public_key() # Message message = b"Hello, world!" # Signature Generation hash_algorithm = hashes.SHA256() signature = private_key.sign( message, algorithm=hash_algorithm ) # Signature Verification try: public_key.verify( signature, message, algorithm=hash_algorithm ) print("Signature is valid.") except: print("Signature is invalid.") The example showcases the generation of a DSA private key, signing a message using the private key, and verifying the signature using the corresponding public key. Depending on the validity of the signature, it will print either “Signature is valid.” or “Signature is invalid.” Output : Signature is valid. This output indicates that the signature verification was successful, and the signature is valid for the given message and public key. Difference between RSA algorithm and DSA : RSA DSA It is a cryptosystem algorithm. It is digital signature algorithm. It is used for secure data transmission. It is used for digital signature and its verification. It was developed in 1977. While it was developed in 1991. It was developed by Ron Rivest, Adi Shamir and Leonard Adleman. It was developed by National Institute of Standards and Technology (NIST). It uses mathematical concept of factorization of product of two large primes. It uses modular exponentiation and discrete logarithm. It is slower in key generation. While it is faster in key generation as compared to RSA. It is faster than DSA in encryption. While it is slower in encryption. It is slower in decryption. While it is faster in decryption. It is best suited for verification and encryption. It is best suited for signing in and decryption. Q2. Explain Diffie-Hellman Key Exchange Algorithm With an Example answer:Diffie-Hellman algorithm: The Diffie-Hellman algorithm is being used to establish a shared secret that can be used for secret communications while exchanging data over a public network using the elliptic curve to generate points and get the secret key using the parameters. For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables, one prime P and G (a primitive root of P) and two private values a and b. P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly. The opposite person receives the key and that generates a secret key, after which they have the same secret key to encrypt. Step-by-Step explanation is as follows: Alice Bob Public Keys available = P, G Public Keys available = P, G Private Key Selected = a Private Key Selected = b Key generated = x = G^a mod P Key generated = y = G^b mod P Exchange of generated keys takes place Key received = y key received = x Generated Secret Key = k_a = y^a mod P Generated Secret Key = k_b = x^b mod P Algebraically, it can be shown that k_a = k_b Users now have a symmetric secret key to encrypt Example: Step 1: Alice and Bob get public numbers P = 23, G = 9 Step 2: Alice selected a private key a = 4 and Bob selected a private key b = 3 Step 3: Alice and Bob compute public values Alice: x =(9^4 mod 23) = (6561 mod 23) = 6 Bob: y = (9^3 mod 23) = (729 mod 23) = 16 Step 4: Alice and Bob exchange public numbers Step 5: Alice receives public key y =16 and Bob receives public key x = 6 Step 6: Alice and Bob compute symmetric keys Alice: ka = y^a mod p = 65536 mod 23 = 9 Bob: kb = x^b mod p = 216 mod 23 = 9 Step 7: 9 is the shared secret. Implementation: /* This program calculates the Key for two persons using the Diffie-Hellman Key exchange algorithm using C++ */ #include #include using namespace std; // Power function to return value of a ^ b mod P long long int power(long long int a, long long int b, long long int P) { if (b == 1) return a; else return (((long long int)pow(a, b)) % P); } // Driver program int main() { long long int P, G, x, a, y, b, ka, kb; // Both the persons will be agreed upon the // public keys G and P P = 23; // A prime number P is taken cout << "The value of P : " << P << endl; G = 9; // A primitive root for P, G is taken cout << "The value of G : " << G << endl; // Alice will choose the private key a a = 4; // a is the chosen private key cout << "The private key a for Alice : " << a << endl; x = power(G, a, P); // gets the generated key // Bob will choose the private key b b = 3; // b is the chosen private key cout << "The private key b for Bob : " << b << endl; y = power(G, b, P); // gets the generated key // Generating the secret key after the exchange // of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); // Secret key for Bob cout << "Secret key for the Alice is : " << ka << endl; cout << "Secret key for the Bob is : " << kb << endl; return 0; } // This code is contributed by Pranay Arora Output: The value of P : 23 The value of G : 9 The private key a for Alice : 4 The private key b for Bob : 3 Secret key for the Alice is : 9 Secret Key for the Bob is : 9 Q3. Explain Digital Signature Algorithm (DSA) With an Example. answer:A Digital Signature is a verification method made by the recipient to ensure the message was sent from the authenticated identity. When a customer signs a check, the bank must verify that he issued that specific check. In this case, a signature on a document acts as a sign of authentication and verifies that the document is authentic. Suppose we have: Alice is the entity that sends a message or initiates communication. Bob represents the recipient or receiver of the message. Eve represents an eavesdropper or adversary who may attempt to intercept or tamper with the communication. In Public Key cryptography (also known as Asymmetric cryptography), the communication process is as follows: Alice encrypts the message using Bob’s public key. The encrypted message reaches Bob. Bob decrypts the message sent by Alice using his private key. Now, suppose when Alice sends a message to Bob, then Bob will check if the sender is authentic; to ensure that it was Alice who sent the message, not Eve. For this, Bob can ask Alice to sign the message electronically. So we can say that an electronic signature can prove that Alice is authentic and is the one sending the message. We called this type of signature a digital signature. What is Digital Signature? Digital Signature is a verification method. Digital signatures do not provide confidential communication. If you want to achieve confidentiality, both the message and the signature must be encrypted using either a secret key or a public key cryptosystem. This additional layer of security can be incorporated into a basic digital signature scheme. Model of Digital Signature Process Model of Digital Signature Process Methods of Digital Signature These two are standard Approaches to implement the Digital Signature: Rivest-Shamir-Adleman (RSA) Digital Signature Algorithm (DSA) Rivest-Shamir-Adleman (RSA) In the RSA approach, the message that needs to be signed is first fed into a hash function that generates a secure hash code of fixed length. The sender’s private key is then used to encrypt the hash code which makes it signature. The next step involves sending both the signature and the message to the intended receiver. For validation purposes, after receiving the message, the recipient first computes its hash-code. The sender’s public key is applied by recipient to decrypt this already encrypted signature. In case if decrypted signature corresponds to recipient-produced hashcode, that means that signature would be considered as valid. Since only the sender has access to the private key, only they could have produced a valid signature. You can refer the below diagram for RSA, here, M = Message or Plaintext H = Hash Function || = bundle the plantext and hash function (hash digest) E = Encryption Algorithm D = Decryption Algorithm PUa = Public key of sender PRa = Private key of sender RSA approach RSA approach Digital Signature Algorithm (DSA) The DSA (Digital Signature Algorithm) approach involves using of a hash function to create a hash code, same as RSA. This hash code is combined with a randomly generated number k as an input to a signature function. The signature function depends on the sender’s private key (PRa) as well as a set of parameters that are known to a group of communicating principals. This set can be considered as a global public key (PUG). The output of the signature function is a signature with two components, s and r. When an incoming message is received, a hash code is generated for the message. This hash code is then combined with the signature and input into a verification function. The verification function depends on the global public key as well as the sender’s public key (PUa) which is paired with the sender’s private key. The output of the verification function returns a value equal to the signature’s component r, if the signature is valid. The signature function is designed in such a way that only the sender, with knowledge of the private key, can produce a valid signature. You can refer below diagram for DSA, where, M = Message or Plaintext H = Hash Function || = bundle the plantext and hash function (hash digest) E = Encryption Algorithm D = Decryption Algorithm PUa = Public key of sender PRa = Public key of sender Sig = Signature function Ver = Verification function PUG = Global public Key DSA Approach DSA Approach Primary Termologies User’s Private Key (PR): This key is publicly known and can be shared with anyone. It’s used to verify digital signatures created with a corresponding private key. User’s Public Key (PU): A top-secret cryptographic key only possessed by the user is used in DSA algorithm’s digital signature generation. As it is, the private key must be kept secret and secure because it proves that a given user is genuine. Signing (Sig): Signing involves creating a digital signature with the help of a user’s private key. In case of DSA, this process requires mathematical operations to be performed on the message that should be signed using a given private key in order to generate a unique signature for that message. Verifying (Ver): Verifying is the process of verifying whether or not a digital signature has been forged using its corresponding public key. In DSA, this involves comparing the messages hash against the verification value through mathematical operations between two binary strings – one representing an encrypted data and another one representing plain-text original message. Steps to Perform DSA The Digital Signature Algorithm (DSA) is a public-key technique (i.e., assymetric cryptography) and it is used to provide only the digital signature function, and it cannot be used for encryption or key exchange. The Steps to perform the Digital Signature Algorithm can be broadly divided into: Global Public-Key Components User’s Private Key User’s Public Key Signing Verifying 1. Global Public-Key Components There are three parameters that are public and can be shared to a set of users. A prime number p is chosen with a length between 512 and 1024 bits such that q divides (p – 1). So, p is prime number where 2L-1 < p <2L for 512<= L<=1024 and L is a multiple of 64; i.e., bit length of between 512 and 1024 bits in increments of 64 bits. Next, an N-bit prime number q is selected. So, q is prime divisor of (p – 1), where 2N-1 < q < 2N i.e., bit length of N bits. Finally, g is selected to be of the form h(p-1)/q mod p, where h is an integer between 1 and (p – 1) with the limitation that g must be greater than 1. So, g is = h(p – 1)/q mod p, where h is any integer with 1 < h < (p – 1) such that h(p-1)/q mod p > 1. If a user has these numbers, then it can selects a private key and generates a public key. 2. User’s Private Key The private key x should be chosen randomly or pseudorandomly and it must be a number from 1 to (q – 1), so x is random or pseudorandom integer with 0 < x < q. 3. User’s Public Key The public key is computed from the private key as y = gx mod p. The computation of y given x is simple. But, given the public key y, it is believed to be computationally infeasible to choose x, which is the discrete logarithm of y to the base g, mod p. 4. Signing If a user want to develop a signature, a user needs to calculates two quantities, r and s, that are functions of the public key components (p, q, g), the hash code of the message H(M, the user’s private key (x), and an integer k that must be generated randomly or pseudorandomly and be unique for each signing. k is generated randomly or pseudorandomly integer such that 0