Encryption is the process of converting information algorithmically so that only a valid recipient can read...

Transcribed Image Text:

Encryption is the process of converting information algorithmically so that only a valid recipient can read the information before it is no longer a valuable secret. This is its validity period. An attacker has limited processing power and can only test a certain number of keys per second. This is the instruction count. The size of the universe of keys divided by the instruction count gives the average time to find a message key. To achieve a balance between the processing power for encryption/decryption and the strength of the encryption, the validity period of the message must be taken into consideration. Given the number of keys, a hijacker can test per second, determine if the encrypted information should remain confidential throughout its validity period. Each test will return two items of information as integers: 1. Can a hijacker crack the code within the period? (1 if true, 0 if false) 2. The strength of the encryption, that is, the number of keys that must be tested to break the encryption. The strength of the encryption is determined as follows: • keys is a list of positive integers, keys[i], that act as keys. The degree of divisibility of an element is the number of elements in the set keys that are greater than 1 and are divisors of the element, i.e. element modulo divisor = 0. ● The element m that has the maximum number of divisors (or degree of divisibility) in keys is used to determine the strength of the encryption. The strength of the encryption is defined as (the degree of divisibility of m) * 105 Notes: • Any divisor of a key must be greater than 1. • The list may contain duplicates. If keys = [2, 4, 4], the divisibility of each 4 element is 3. The 4s are each divisible by all 3 keys[i]. Example instruction Count = 1000 validityPeriod = 10000 n=4 keys = [2, 4, 8, 2] Looking at the elements in keys: 2 is divisible by [2, 2] so its degree of divisibility is 2 4 is divisible by [2, 4, 2] so its degree of divisibility is 3 8 is divisible by [2, 4, 8, 2] so its degree of divisibility is 4 2 is divisible by [2, 2] so its degree of divisibility is 2, as in the first case The element m that has the maximum number of divisors is 8 and its degree of divisibility is 4. The encryption strength is 4 * 105 = 400,000. The hijacker can perform instruction Count = 1,000 calculations per second. During the total validityPeriod = 10,000 seconds, the hijacker can test 1000 * 10000 = 10000000=107 keys. Thus, there is sufficient time for the key to be determined and the message decrypted before its validity expires. The first value in the return array is 1 because the message can be decrypted. The return array is [1, 400000] because the hijacker can decrypt the message in time, and the strength of the encryption is 400000. Function Description Complete the function encryptionValidity in the editor below. encryptionValidity has the following parameter(s): int instructionCount: the number of keys the hijacker can test per second int validityPeriod: the number of seconds the message must be protected int keys[n]: the keys for encryption/decryption Returns: int[2]: result[0] contains 1 = True or 0= False depending on the hijacker's success, followed by the encryption strength in result[1]. Constraints ● 1 ≤ instruction Count, validityPeriod ≤ 108 • 1≤n≤105 • 1 ≤ keys[i] ≤ 105 Encryption is the process of converting information algorithmically so that only a valid recipient can read the information before it is no longer a valuable secret. This is its validity period. An attacker has limited processing power and can only test a certain number of keys per second. This is the instruction count. The size of the universe of keys divided by the instruction count gives the average time to find a message key. To achieve a balance between the processing power for encryption/decryption and the strength of the encryption, the validity period of the message must be taken into consideration. Given the number of keys, a hijacker can test per second, determine if the encrypted information should remain confidential throughout its validity period. Each test will return two items of information as integers: 1. Can a hijacker crack the code within the period? (1 if true, 0 if false) 2. The strength of the encryption, that is, the number of keys that must be tested to break the encryption. The strength of the encryption is determined as follows: • keys is a list of positive integers, keys[i], that act as keys. The degree of divisibility of an element is the number of elements in the set keys that are greater than 1 and are divisors of the element, i.e. element modulo divisor = 0. ● The element m that has the maximum number of divisors (or degree of divisibility) in keys is used to determine the strength of the encryption. The strength of the encryption is defined as (the degree of divisibility of m) * 105 Notes: • Any divisor of a key must be greater than 1. • The list may contain duplicates. If keys = [2, 4, 4], the divisibility of each 4 element is 3. The 4s are each divisible by all 3 keys[i]. Example instruction Count = 1000 validityPeriod = 10000 n=4 keys = [2, 4, 8, 2] Looking at the elements in keys: 2 is divisible by [2, 2] so its degree of divisibility is 2 4 is divisible by [2, 4, 2] so its degree of divisibility is 3 8 is divisible by [2, 4, 8, 2] so its degree of divisibility is 4 2 is divisible by [2, 2] so its degree of divisibility is 2, as in the first case The element m that has the maximum number of divisors is 8 and its degree of divisibility is 4. The encryption strength is 4 * 105 = 400,000. The hijacker can perform instruction Count = 1,000 calculations per second. During the total validityPeriod = 10,000 seconds, the hijacker can test 1000 * 10000 = 10000000=107 keys. Thus, there is sufficient time for the key to be determined and the message decrypted before its validity expires. The first value in the return array is 1 because the message can be decrypted. The return array is [1, 400000] because the hijacker can decrypt the message in time, and the strength of the encryption is 400000. Function Description Complete the function encryptionValidity in the editor below. encryptionValidity has the following parameter(s): int instructionCount: the number of keys the hijacker can test per second int validityPeriod: the number of seconds the message must be protected int keys[n]: the keys for encryption/decryption Returns: int[2]: result[0] contains 1 = True or 0= False depending on the hijacker's success, followed by the encryption strength in result[1]. Constraints ● 1 ≤ instruction Count, validityPeriod ≤ 108 • 1≤n≤105 • 1 ≤ keys[i] ≤ 105