Instructions
Requirements and Specifications
- File format - one doc file, and the file should contain source code(s), and output captures.
- Upload your file into the D2L
- Compiles - if it does not compile, it will not be graded
- Electronic submission correct (including file formats) - if not, it will not be graded
- When writing programs, you may consult with me or the GA at any stage of your program development. It helps if you bring a current print-out.
- Any student caught cheating on program will automatically fail the course and may be referred to the department chair and/or dean.
- To avoid cheating via collaboration, do not show any other classmates your code. If a classmate consults you for help with C++ assignment after attempting to run his or her program, you may assist in determining why his or her code doesn't work, but refrain from suggesting specific new code.
- Do not lead your classmates into temptation: guard your print-outs. We intend to use an automatic cheating-verification program that is capable of detecting partial logical similarities. Don't even take the risk.
- The following ciphertext was the output of a shift cipher:
- The following was encrypted using by row transposition method. Implemented functions to perform encryption/decryption.
- Encryption the plaintext = “attack postponed until two am” using double transposition with the key (4, 3, 1, 2, 5, 6, 7).
- Decrypt the ciphertext “AMRT MOEP EAEG RTFY TZTY XAWE” using double transposition with the key (3 5 1 6 2 4).
- Implement functions to perform encryption/decryption with 2x2 Hill Cipher. The key should be an invertible matrix over the integers mod 26.
- Show the output of your encrypt function on the following (key, plaintext) pair:
Source Code
#include
#include
#include
#include
#include
#include
#include
// Classical Encryption Techniques:
// 1.
struct CipherFreqTable {
char letter[26];
float freq[26];
};
int mod(int x, int y) {
if (x < 0) {
while (x < 0) x += y;
return x;
} else {
return x % y;
}
}
CipherFreqTable* letter_freq(const char* p) {
CipherFreqTable* t = new CipherFreqTable;
for (int i = 0; i < 26; i += 1) {
t->letter[i] = 'A' + i;
t->freq[i] = 0;
}
for (int i = 0; i < strlen(p); i += 1) {
int j = p[i] - 'A';
t->freq[j] += 1;
}
return t;
}
char* shift_decrypt(const char* c, int k) {
int c_size = (int)strlen(c);
char* p = (char*)malloc(sizeof(c) * c_size + 1);
p[c_size] = 0;
for (size_t i = 0; i < c_size; i += 1) {
p[i] = mod((c[i] - 'A') - k, 26) + 'a';
}
return p;
}
//*************************************************************************************//
// 2.
char* expand_string(char* str, int desired_size) {
int str_size = (int)strlen(str);
char* s = (char*)malloc(sizeof(char) * desired_size + 1);
s[desired_size] = 0;
for (int i = 0; i < desired_size; i += 1) {
s[i] = (i < str_size) ? str[i] : 'x';
}
return s;
}
char* row_transposition_encrypt(char* _P, int* K, int k_size) {
int p_size = strlen(_P);
int pad = ((p_size % k_size) != 0) ? k_size - (p_size % k_size) : 0;
int c_size = p_size + pad;
char* P = expand_string(_P, c_size);
char* C = (char*)malloc(c_size + 1);
C[c_size] = 0;
char** TBL = (char**)malloc(sizeof(char*) * (c_size / k_size));
for (int i = 0; i < (c_size / k_size); i += 1) {
char* p_ptr = P + (i * k_size);
TBL[i] = (char*)malloc(sizeof(char) * k_size);
for (int j = 0; j < k_size; j += 1) {
TBL[i][j] = p_ptr[j];
}
}
int k = 0;
for (int i = 0; i < k_size; i += 1) {
int c = 0;
for (int j = 0; j < k_size; j += 1) {
if (K[j] == i + 1) {
c = j;
break;
}
}
for (int j = 0; j < (c_size / k_size); j += 1) {
C[k++] = TBL[j][c];
}
}
return C;
}
char* row_transposition_decrypt(char* C, int* K, int k_size) {
int c_size = strlen(C);
int p_size = c_size;
char* P = (char*)malloc(p_size + 1);
P[p_size] = 0;
char** TBL = (char**)malloc(sizeof(char*) * (c_size / k_size));
for (int i = 0; i < (c_size / k_size); i += 1) {
char* c_ptr = C + (i * k_size);
TBL[i] = (char*)malloc(sizeof(char) * k_size);
}
for (int i = 0; i < k_size; i += 1) {
char* c_ptr = C + (i * (c_size / k_size));
for (int j = 0; j < (c_size / k_size); j += 1) {
TBL[j][K[i] - 1] = c_ptr[j];
}
}
int k = 0;
for (int i = 0; i < (c_size / k_size); i += 1) {
for (int j = 0; j < k_size; j += 1) {
P[k++] = TBL[i][j];
}
}
return P;
}
//*************************************************************************************/
// Hill cipher
int mult_inv(int i) {
int k = 0;
int j = 0;
for (j = 0; j < 26; j += 1) {
k = (i * j);
if (k % 26 == 1) break;
}
return j;
}
struct Mat22 {
int data[2][2];
};
Mat22* mat22_set(int a, int b, int c, int d) {
Mat22* m = (Mat22*)malloc(sizeof(Mat22));
m->data[0][0] = a;
m->data[0][1] = b;
m->data[1][0] = c;
m->data[1][1] = d;
return m;
}
void mat22_print(Mat22* m) {
std::cout << "|" << std::setw(2) << (m->data[0][0]) << " " << std::setw(2) << (m->data[0][1]) << "|";
std::cout << "\n";
std::cout << "|" << std::setw(2) << (m->data[1][0]) << " " << std::setw(2) << (m->data[1][1]) << "|";
std::cout << "\n";
}
Mat22* mat22_mul(Mat22* m, Mat22* n) {
Mat22* o = (Mat22*)malloc(sizeof(Mat22));
o->data[0][0] = mod((m->data[0][0] * n->data[0][0]) + (m->data[0][1] * n->data[1][0]), 26);
o->data[0][1] = mod((m->data[0][0] * n->data[0][1]) + (m->data[0][1] * n->data[1][1]), 26);
o->data[1][0] = mod((m->data[1][0] * n->data[0][0]) + (m->data[1][1] * n->data[1][0]), 26);
o->data[1][1] = mod((m->data[1][0] * n->data[0][1]) + (m->data[1][1] * n->data[1][1]), 26);
return o;
}
Mat22* mat22_adj(Mat22* m) {
Mat22* adj = (Mat22*)malloc(sizeof(Mat22));
adj->data[0][0] = m->data[1][1];
adj->data[0][1] = m->data[0][1] * -1;
adj->data[1][0] = m->data[1][0] * -1;
adj->data[1][1] = m->data[0][0];
return adj;
}
// inv = (1/(ad - bc))[a1 a2]
// [b1 b2]
Mat22* mat22_inv(Mat22* m) {
Mat22* inv = mat22_adj(m);
int denom = mod((m->data[0][0] * m->data[1][1]) - (m->data[0][1] * m->data[1][0]), 26);
int inverse = mult_inv(denom);
inv->data[0][0] = mod(inv->data[0][0] * inverse, 26);
inv->data[0][1] = mod(inv->data[0][1] * inverse, 26);
inv->data[1][0] = mod(inv->data[1][0] * inverse, 26);
inv->data[1][1] = mod(inv->data[1][1] * inverse, 26);
return inv;
}
char* hillcipher_encrypt(char* P, Mat22* K) {
int p_size = (int)strlen(P);
char* C = (char*)malloc(sizeof(char) * p_size + 1);
C[p_size] = 0;
// encode C = P*K
int i = 0;
int j = 0;
for (; i < p_size; i += 4) {
Mat22* p_mat = mat22_set(P[i + 0] - 'a',
(i + 1 < p_size) ? P[i + 1] - 'a' : 0,
(i + 2 < p_size) ? P[i + 2] - 'a' : 0,
(i + 3 < p_size) ? P[i + 3] - 'a' : 0);
Mat22* c_mat = mat22_mul(p_mat, K);
if (i < p_size) C[j++] = c_mat->data[0][0] + 'A';
if (i + 1 < p_size) C[j++] = c_mat->data[0][1] + 'A';
if (i + 2 < p_size) C[j++] = c_mat->data[1][0] + 'A';
if (i + 3 < p_size) C[j++] = c_mat->data[1][1] + 'A';
free(p_mat);
free(c_mat);
}
return C;
}
char* hillcipher_decrypt(char* C, Mat22* inv_K) {
int c_size = (int)strlen(C);
char* P = (char*)malloc(sizeof(char)* c_size + 1);
P[c_size] = 0;
// add padding to C
int pad = 0;
while ((c_size + pad) % 4 != 0) {
pad += 1;
C = (char*)realloc(C, c_size + pad);
C[c_size + pad - 1] = ' ';
}
// decode P = C*K^(-1)
int i = 0;
int j = 0;
for (; i < c_size; i += 4) {
Mat22* c_mat = mat22_set((i + 0 < c_size) ? C[i + 0] - 'A' : 0,
(i + 1 < c_size) ? C[i + 1] - 'A' : 0,
(i + 2 < c_size) ? C[i + 2] - 'A' : 0,
(i + 3 < c_size) ? C[i + 3] - 'A' : 0);
Mat22* p_mat = mat22_mul(c_mat, inv_K);
if (i + 0 < c_size) P[j++] = p_mat->data[0][0] + 'a';
if (i + 1 < c_size) P[j++] = p_mat->data[0][1] + 'a';
if (i + 2 < c_size) P[j++] = p_mat->data[1][0] + 'a';
if (i + 3 < c_size) P[j++] = p_mat->data[1][1] + 'a';
free(c_mat);
free(p_mat);
}
return P;
}
//*************************************************************************************//
int main() {
{
const char* ciphertext = "LCLLEWLJAZLNNZMVYIYLHRMHZA";
// frequency analysis
int k = -1;
CipherFreqTable* freq_table = letter_freq(ciphertext);
int score = 0;
char letter = ' ';
for (size_t j = 0; j < 26; j += 1) {
if (score < freq_table->freq[j]) {
score = freq_table->freq[j];
letter = freq_table->letter[j];
}
}
letter += 32;
k = letter - 'e';
char* plaintext = shift_decrypt(ciphertext, k);
std::cout << "\n";
std::cout << "Question 1 " << "\n";
std::cout << "Using a frequency count the key was foudn to be " << k << "\n";
std::cout << "The message was encrypted to:" << plaintext << "\n\n";
}
//*********************************
{
int key[] = {4, 3, 1, 2, 5, 6, 7};
char P[] = "attackpostponeduntiltwoam";
char* C1 = row_transposition_encrypt(P, key, 7);
char* C = row_transposition_encrypt(C1, key, 7);
std::cout << "\n";
std::cout << "Question 2.a " << "\n";
// char str[] = C1;
char ch[]={};
for (int i = 0; i < strlen(C); i++) {
ch[i] = toupper(C[i]);
}
std::cout << "The message was encrypted to: " << ch << "\n\n";
char* _P = row_transposition_decrypt(row_transposition_decrypt(C, key, 7), key, 7);
}
{
int key[] = {3, 5, 1, 6, 2, 4};
char C[] = "amrtmoepeaegrtfytztyxawe";
char* P = row_transposition_decrypt(row_transposition_decrypt(C, key, 6), key, 6);
//std::cout << "Key :: ";
for (int i = 0; i < 6; i += 1) {
//std::cout << key[i] << " ";
}
std::cout << "\n";
std::cout << "Question 2.b " << "\n";
std::cout << "The message was encrypted to: " << P << "\n\n";
}
//*********************************
{
Mat22* K = mat22_set(9, 4, 5, 7);
char P[] = "meetmeattheusualplaceattenratherthaneightoclockx";
char* C = hillcipher_encrypt(P, K);
std::cout << "\n";
std::cout << "Question 3.a " << "\n";
std::cout << "Ciphertext: " << C << "\n\n";
free(K);
free(C);
}
//*********************************
{
Mat22* K = mat22_set(9, 13, 2, 3);
char* C = (char*)malloc(sizeof(char) * 6);
memcpy(C, "YIFZMA", 6);
Mat22* inv_K = mat22_inv(K);
Mat22* identity = mat22_mul(K, inv_K);
char* P = hillcipher_decrypt(C, inv_K);
std::cout << "\n";
std::cout << "Question 3.b " << "\n";
std::cout << "Plaintext: " << P << "\n";
free(inv_K);
free(K);
free(P);
}
//*********************************
{
// known plaintext attack
char P[] = "howareyoutoday";
char C[] = "ZWSENIUSPLJVEU";
Mat22* p_mat = mat22_set(P[0] - 'a', P[1] - 'a', P[8] - 'a', P[9] - 'a');
Mat22* inv_p_mat = mat22_inv(p_mat);
Mat22* identity_of_p = mat22_mul(p_mat, inv_p_mat);
Mat22* c_mat = mat22_set(C[0] - 'A', C[1] - 'A', C[8] - 'A', C[9] - 'A');
Mat22* K = mat22_mul(inv_p_mat, c_mat);
std::cout << "\n";
std::cout << "Question 4 " << "\n";
std::cout << "Key: \n";
mat22_print(K);
std::cout << "\n";
}
return 0;
}