Fcaassignment2 Thomas Sampson

Computer Architecture – Assignment 2 Encryption!

Thomas Sampson – Games Software Development – 2Y - 2007

My Encryption Code Below is the encryption algorithm number 14 (written in x86 assembly), which I was allocated along with the encryption key „n‟. I have commented my encryption routine below to explain how it works. encrypt14: push edx

// the value of the edx register is pushed onto the stack for safe keeping

/* Inputs: EAX = Encryption Key Value, ECX = Source character to be encrypted Outputs: EAX = Encrypted character Before this sub routine was called, the source character (the character being encrypted) was pushed into the ECX register with the “movsx” (move with sign extension) instruction. Characters are only 8 bits in length. Therefore the source character only occupies the “CL” region of the EXC register (the last 8 bits of the register). The encryption key was also saved in the EAX register using the “movsx” instruction, again only occupying the last 8 bits of the register (“AL”). */ // Rotate the 8bit source character in CL one position to the right ror cl,1 // Rotate the 8bit source character in CL one position to the right ror cl,1

ror cl,1

// Rotate the 8bit source character in CL one position to the right

ror cl,1

// Rotate the 8bit source character in CL one position to the right

push ecx

//Push the new rotated/encrypted value of ECX (source character) onto the stack

add eax,0x55

//The value 55h (or 85 in denary) is added to the EAX register (the encryption key) and the result over written to the EAX register //The value of EAX (encryption key + 55h) is copied into the EDX register //The last item on the stack (the scrambled character) is popped off the stack into the EAX register //This compares each bit inside the EAX (scrambled source character) register with each bit inside the EDX (encryption key + 55h) register, producing a result of 1 for each set of different bits (e.g. a 0 compared to a 1) and a result of 0 for each pair of matching bits (e.g. comparing 1 with 1). The result is then stored inside EAX. //The 8 bits of AL (final 8 bits of EAX), which represent the result of the XOR, are rotated one position to the right //The 8 bits of AL (final 8 bits of EAX), which represent the result of the XOR, are again rotated one position to the right

mov edx,eax pop eax xor eax,edx

ror al,1 ror al,1 not al

//Inverts each bit inside the AL section of the EAX register, setting any 0‟s to 1‟s and all 1‟s to 0‟s.

add eax,0x10

//Adds 10h (16 in denary) to the value inside EAX

pop edx

// Restored the old value of EDX from the stack to tidy up ready for ending the sub routine

ret

//Uses the return location on the stack to swap the EIP (instruction pointer) register back to the position from where this sub routine was called.

Implementing the Standard Call mechanism Instead of using registers to pass parameters to my sub routine, below I have implemented the standard call procedure which uses the stack to send parameters into my sub routine. NOTE: - At this point I am only implementing _stdcall and not optimising any of the code

Part 1 This part of the code is responsible for organising the stack / calling the sub routine, and resides inside the while loop. __asm { push ecx push edx

//push or 'save' the value of ecx onto the stack //push or 'save' the value of edx onto the stack

push EKey; push s_char;

//push parameter 1 (the encryption key) onto the stack //push parameter 2 (the source char) onto the stack

call encrypt14; //call sub routine with result stored in EAX or „AL‟ to be precise add esp,8; //push the stack pointer back (by 8 as we used 2*4byte paramaters) mov e_char, al; //move the encrypted character into variable 'e_char' pop edx; pop ecx; }

//pop or 'restore' the old value of edx from the stack //pop or 'restore' the old value of ecx from the stack

Part 2 This part of the code is the actual sub routine itself „encrypt14‟ which now gets its parameters from the stack rather than using registers.

__asm { encrypt14: push ebp; mov ebp, esp;

//push old base pointer value onto stack //move base pointer to current stack pointer

//----Main Encrytion Routine----// mov ecx, dword ptr [ebp+8]; //place the source character in ecx mov eax, dword ptr [ebp+0Ch]; //place the encryption key in eax ror ror ror ror

cl, cl, cl, cl,

1; 1; 1; 1;

push ecx add eax,0x55 mov edx,eax pop eax xor eax,edx ror al,1 ror al,1 not al add eax,0x10

//rotate the source character bits right 4 times

//run main encryption routine (commented previously)

//--End Main Encryption Routine--// mov esp, ebp; pop ebp; ret;

//set stack pointer back to base pointer //restore the old base pointer from stack //end sub routine, also pops return address off the stack

}

Note: - The encrypted character is returned by storage in the EAX register as this is standard practice when using the _stdcall mechanism.

Encryption Routine To work out a method of decrypting the character I first decided to draw a simple flow chart of how the source character is encrypted, allowing me to reverse the process.

Source Character  CL CL – ROR x 4

Stack CL pushed onto stack

Encryption Key  AL AL – Add 55h AL – Copied into DL AL – Now = CL

XOR AL with DL AL =Scrambled source char DL = Encryption Key + 55h

Result into AL

AL – ROR x 2 NOT AL AL + 10h

Encrypted key is now in AL

CL popped off of stack

Decryption Routine From the previous flow chart I could not devise the following decryption routine by reversing the encryption process. Encrypted character  AL Encryption Key  CL AL subtract 10h NOT AL ROL AL x2 CL add 55h

XOR AL with CL AL =Jumbled Key CL = Encryption Key + 55h

Result into AL

ROL AL x4

Decrypted key is now in AL

Implementing Decryption Routine in Assembly I now implemented my decryption routine in x86 assembly, again using the _stdcall mechanism Part 1

__asm { push ecx push edx;

//push or 'save' the value of ecx onto the stack //push or 'save' the value of edx onto the stack

push key; push e_char;

//push parameter 1 (the encryption key) onto the stack //push parameter 2 (the encrypted char) onto the stack

call decrypt14;

//call decryption sub routine, with result stored in EAX

add esp,8; mov e_char, al;

//push the stack pointer back (using 8 as we used 2 parameters) //move the encrypted character into variable 'e_char'

pop edx; pop ecx;

//pop or 'restore' the old value of edx from the stack //pop or 'restore' the old value of ecx from the stack

}

Part 2

__asm { decrypt14: push ebp; mov ebp, esp;

//push old base pointer value onto stack //move base pointer to current stack pointer

//----Main Decrytion Routine----// mov eax, dword ptr [ebp+8]; mov ecx, dword ptr [ebp+0Ch]; sub not rol add xor rol

al, 10h; al; al, 2; ecx, 55h; eax, ecx; al, 4;

//put paramater 1 (encrypted char) in EAX //put parameter 2 (encryption key) in ECX

//minus ten from the encrypted character (to undo add 10h) //invert encrytped char (to undo previous not operation) //rotate left x2 (to undo rotate right x2) //Add 55h to the encryptio key (we need it in this state) //Compare (key +55h) with (modified encrypted char) //Rotate the aswer right x4 (to undo previous ror x4)

//--End Main Decryption Routine--// mov esp, ebp; pop ebp; ret;

//set stack pointer back to base pointer //restore the old base pointer from stack //end sub routine

}

Note: - The decrypted character is returned by storage in the EAX register as this is standard practice when using the _stdcall mechanism.

Optimising my code I will now attempt to optimise the assembly code used in both the encryption and decryption routines to increase efficiency and reduce the code footprint. Encryption Routine Optimisation __asm { push ecx push EKey; push s_char;

//push or 'save' the value of ecx onto the stack //push parameter 1 (the encryption key) onto the stack //push parameter 2 (the source char) onto the stack

call encrypt14; //call sub routine with result stored in EAX or „AL‟ to be precise add esp,8; //push the stack pointer back (by 8 as we used 2*4byte paramaters) mov e_char, al; //move the encrypted character into variable 'e_char' pop ecx; //pop or 'restore' the old value of ecx from the stack } In the main “encrypt14” routine I removed the use of the register edx, therefore removed the process of pushing and popping it off the stack when calling the sub routine. There is no point in saving the value of EDX on the stack and retrieveing it after the function call, as I am confident that the value of EDX will not be changed during the sub routine.

__asm { encrypt14: push ebp; mov ebp, esp;

//push old base pointer value onto stack //move base pointer to current stack pointer

//----Main Encrytion Routine----// mov ecx, dword ptr [ebp+8]; //place the source character in ecx mov eax, dword ptr [ebp+0Ch]; //place the encryption key in eax Here I used the second operand of “ror” to inform the instruction to do 4 rotations to the right, instead of repeating the operation 4 times ror cl, 4; //rotate the source character bits right 4 times Here I removed the process of pushing ECX onto the stack as it served no relevant purpose add al,0x55 Here I removed the process of copying EAX into EDX as it was un-necessary As a consequence of not putting ECX on the stack, and not using EDX, I can now use the XOR function on EAX and ECX (this has exactly the same effect as the previous convoluted method) xor al,cl Here I used the second operand of “ror” to inform the instruction to do 2 rotations to the right, instead of repeating the operation twice ror al,2 not al add al,0x10 //--End Main Encryption Routine--// mov esp, ebp; pop ebp; ret;

//set stack pointer back to base pointer //restore the old base pointer from stack //end sub routine, also pops return address off the stack

} Note: - For all manipulations of EAX and ECX I changed all the references to AL and CL (the latter byte of the registers). This should make arithmentic and XOR functions more efficient as they do not have to work with 32 bits of data, only 8.

Decryption Routine Optimisation __asm { push ecx push key; push e_char;

//push or 'save' the value of ecx onto the stack //push parameter 1 (the encryption key) onto the stack //push parameter 2 (the encrypted char) onto the stack

call decrypt14;

//call decryption sub routine, with result stored in EAX

add esp,8; mov e_char, al; pop ecx;

//push the stack pointer back (using 8 as we used 2 parameters) //move the encrypted character into variable 'e_char' //pop or 'restore' the old value of ecx from the stack

} Again, here I removed the process of saving and restoring EDX, which takes time saving the value to the stack (main memory). Again, I made this decision as I am confident that “decrypt14” does not make use of the EDX register.

__asm { decrypt14: push ebp; mov ebp, esp;

//push old base pointer value onto stack //move base pointer to current stack pointer

//----Main Decrytion Routine----// mov eax, dword ptr [ebp+8]; mov ecx, dword ptr [ebp+0Ch]; sub not rol add xor rol

al, al; al, cl, al, al,

10h; 2; 55h; cl; 4;

//put paramater 1 (encrypted char) in EAX //put parameter 2 (encryption key) in ECX

//minus ten from the encrypted character (to undo add 10h) //invert encrytped char (to undo previous not operation) //rotate left x2 (to undo rotate right x2) //Add 55h to the encryptio key (we need it in this state) //Compare (key +55h) with (modified encrypted char) //Rotate the aswer right x4 (to undo previous ror x4)

//--End Main Decryption Routine--// mov esp, ebp; pop ebp; ret;

//set stack pointer back to base pointer //restore the old base pointer from stack //end sub routine

}

When I wrote this routine I tried to make it as optimised as possible, however here I have again changed all references to EAX and ECX to AL and CL to reduce the number of bits being manipulated, hence increasing efficiency. I have also made use of the second operand of ROR and ROL to group together these instructions.

Lower Case Conversion The c++ code is responsible for checking that the string we enter contains ONLY alpha numeric characters. To do lower case conversion (during decryption) we must isolate any uppercase characters and convert them. Uppercase characters lie within the ASCII code region of 0x41  0x5A. In the assembly code I do two checks to ensure the character lies within these bounds, only if it meets these conditions will it be converted to lowercase, otherwise the IP will jump to the end of the decryption routine, bypassing any case conversion. Lowercase conversion is easy as there is a direct link between lower and uppercase ASCII codes. Any uppercase ASCII code + 0x20 gives its lowercase equivalent, (a simple addition to the AL region of the EAX register).

add ecx, 55h; xor eax, ecx; rol al, 4; cmp al, 41h; jl fail; cmp al, 5Ah; jg fail; add al, 20h; fail:

End of decryption logic // the decrypted characater with 41h //if decrypted char is <41h then jump to „fail‟ //compare the decrypted characater with 5Ah //if decrypted char is >5Ah then jump to „fail‟ //+20h to decrypted char (shift to lower case) //The decrypted character is NOT a captial

mov esp, ebp; pop ebp; ret;

End of decryption sub routine