UTS Programming Competition 2013 Problem 3

From ProgSoc Wiki

Jump to: navigation, search

Problem 3: Known Plaintext

Problem Description

You work for GCHQ (Genius Cryptographers HeadQuarters), an organisation that cracks codes for a living. With the advent of computers, GCHQ hopes to increase productivity by automating all the old well-known code cracking techniques. You have been given the task of writing a program that carries out known plaintext attacks for substitution ciphers. In a known plaintext attack, you have in your possession one plaintext (original, unencrypted) message, and its corresponding ciphertext (the encrypted message). You can use this information to extract a key that can be used to decipher other messages for which you don't have the plaintext.

Your program will be used only for monoalphabetic substitution ciphers. A monoalphabetic substitution cipher is one in which each letter of the alphabet is replaced by another unique letter of the same alphabet. Every instance of the letter 'A' in the plaintext message will be replaced by the same letter in the ciphertext, and so on. Similarly, when decrypting, every instance of the letter 'A' in the ciphertext will be replaced by the same letter in the plaintext, and so on.

Problem Task

The first line of input is a plaintext message of less than 80 characters.

The second line of input is the ciphertext that corresponds to the plaintext message on the previous line. For this task, all plaintext and ciphertext messages will consist of uppercase letters and spaces only.

The third line of input is an integer N, indicating the number of new ciphertexts you need to decipher.

The following N input lines will be new ciphertexts that you need to decipher, one per line. They are all less than 80 characters in length, and all use the same substitution rules as the ciphertext you read in on the second line.

For each new ciphertext, decipher it and print the plaintext message on a single line. If the ciphertext contains a character that you don't know the substitution for, replace it with a question mark in the plaintext output.

Sample Input

DO NOT TELL ANYONE ABOUT OUR CODE I WILL MEET YOU IN SAN FRANCISCO TOMORROW
EP OPU UFMM BOZPOF BCPVU PVS DPEF J XJMM NFFU ZPV JO TBO GSBODJTDP UPNPSSPX
3
MBOE
IFMMP
J BN BO BGSJDBO QSJODF BOE J OFFE ZPVS IFMQ UP HFU NZ JOIFSJUBODF

Sample Output

LAND
?ELLO
I AM AN AFRICAN ?RINCE AND I NEED YOUR ?EL? TO ?ET MY IN?ERITANCE

N.B. The key used for the sample input and output is a Caesar cipher, in which the alphabet is rotated several places. Caesar ciphers are a small subset of all monoalphabetic substitution ciphers. In particular, the cipher used by the judges for testing is not guaranteed to be a Caesar cipher – it could be any monoalphabetic substitution cipher.

Solutions

Put your solutions here!

Personal tools