NetworkXOneTimePad
SRM 516 · 2011-05-25 · by dolphinigle
SRM 516 · 2011-05-25 · by dolphinigle · Brute Force, Encryption/Compression, Greedy
Problem Statement
Problem Statement
One-time pad (patented by Vernam in 1919) is one of the most widely known schemes to encrypt a binary string to achieve confidentiality. This scheme takes a binary string (a string consisting of only the digits 0 and 1) as input and outputs another binary string of the same length. The input is called the plaintext, and the output is called the ciphertext. The scheme uses a key which is another binary string of the same length as the input. The i-th bit of the ciphertext is defined as the XOR of the i-th bit of the plaintext and the key (see the notes for XOR definition). The ciphertext is sent to the receiving party.
In this problem, we will consider several messages, each of length N, encrypted using a single key of length N.
We would like to investigate how strong this cipher is. Suppose an adversary manages to find out the content of all the original messages (i.e., the plaintexts) and some of the encrypted messages (i.e., ciphertexts). These messages are given in theString[] s plaintexts and ciphertexts, respectively. Return the number of possible keys that are consistent with this data. The constraints will guarantee that there is at least one such key. A key is consistent if for all members of ciphertexts C, there exists a member of plaintexts P such that when P is encrypted using the specified key, it becomes C.
In this problem, we will consider several messages, each of length N, encrypted using a single key of length N.
We would like to investigate how strong this cipher is. Suppose an adversary manages to find out the content of all the original messages (i.e., the plaintexts) and some of the encrypted messages (i.e., ciphertexts). These messages are given in the
Notes
- XOR is a binary operation on bits defined as follows: 0 XOR 0 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0.
Constraints
- plaintexts will contain between 1 and 50 elements, inclusive.
- Each element of plaintexts will contain between 1 and 50 characters, inclusive.
- All the elements of plaintexts will contain the same number of characters.
- All the characters in plaintexts will be either '0' (zero) or '1' (one).
- All the elements of plaintexts will be distinct.
- ciphertexts will contain between 1 and 50 elements, inclusive.
- All the elements of ciphertexts will contain the same number of characters as all the elements of plaintexts.
- All the characters in ciphertexts will be either '0' (zero) or '1' (one).
- All the elements of ciphertexts will be distinct.
- There will exist at least one key that is consistent with the given plaintexts and ciphertexts.
Examples
0)
{"110", "001"}
{"101", "010"}
Returns: 2
The two possible keys are "011" and "100".
1)
{"00", "01", "10", "11"}
{"00", "01", "10", "11"}
Returns: 4
2)
{"01", "10"}
{"00"}
Returns: 2
3)
{"000", "111", "010", "101", "110", "001"}
{"011", "100"}
Returns: 6
4)
{"0"}
{"1"}
Returns: 1
Submissions are judged against all 142 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NetworkXOneTimePad with a public method int crack(vector<string> plaintexts, vector<string> ciphertexts) · 142 test cases · 2 s / 256 MB per case