##################################################################################################################################################################
#                                                      Simplified Data Encryption Standard (S-DES)                                                               #
#                                                                                                                                                                #
# The process of encrypting a plaintext using S-DES is illustrated with an example which may help you to understand it as easily as possible. Similarly to Data  #
# Encryption Standard (DES), S-DES is a block cipher. It has 8-bits block size of plaintext or ciphertext, it uses 10-bits key size for encryption and it has    #
# two rounds.                                                                                                                                                    #
#################################################################################################################################################################

###########################
# Key Generation of S-DES #
###########################

##########################################################################################
# Step 1: Select a random key of 10-bits. Permute the bits in K using the table.         #
# Input position  1 2 3 4 5 6 7 8 9 10                                                   #
# Output position 3 5 2 7 4 10 1 9 8 6                                                   #
##########################################################################################

def initalPermKey(keyIn):
    permArr = [3,5,2,7,4,10,1,9,8,6]
    returnKey = ""
    for i in range(len(permArr)):
        returnKey = returnKey + keyIn[permArr[i] - 1]
    return returnKey

#####################################################################
# Step 2: Divide the key into two halves, left half and right half  #
#####################################################################

def splitKey(keyIn):
    returnArr = []
    keyLeft = ""
    keyRight = ""
    for i in range(len(keyIn)/2):
        keyLeft = keyLeft + keyIn[i]
        keyRight = keyRight + keyIn[len(keyIn)/2 + i]
    returnArr.append(keyLeft)
    returnArr.append(keyRight)
    return returnArr

######################################################
# Step 3: Apply the one bit Round shift on each half #
######################################################

def rotateSplitKeyBy1(arrIn):
    keyLeft = arrIn[0]
    keyRight = arrIn[1]
    newLeft = ""
    newRight = ""
    for i in range(len(keyLeft)):
        newLeft = newLeft + keyLeft[((i+1) % len(keyLeft))]
        newRight = newRight + keyRight[((i+1) % len(keyRight))]
    returnArr = []
    returnArr.append(newLeft)
    returnArr.append(newRight)
    return returnArr

#####################################################################################################
# Step 4: Combine both halves of the bits, right and left and permute using the permutation table.  #
# Position 1 2 3 4 5 6 7 8 9 10                                                                     #
# Position used for the output 6 3 7 4 8 5 10 9                                                     #
#####################################################################################################

def extractRK(arrIn):
    tempKey = ""
    tempKey = tempKey + arrIn[0]
    tempKey = tempKey + arrIn[1]
    RK = ""
    bitsUsed = [6,3,7,4,8,5,10,9]
    for i in range(len(bitsUsed)):
        RK = RK + tempKey[((bitsUsed[i])-1)]
    return(RK)


######################################################
# Step 5: Apply the two bit Round shift on each half #
######################################################
def rotateSplitKeyBy2(arrIn):
    keyLeft = arrIn[0]
    keyRight = arrIn[1]
    newLeft = ""
    newRight = ""
    for i in range(len(keyLeft)):
        newLeft = newLeft + keyLeft[((i+2) % len(keyLeft))]
        newRight = newRight + keyRight[((i+2) % len(keyRight))]
    returnArr = []
    returnArr.append(newLeft)
    returnArr.append(newRight)
    return returnArr

##################################################################################################################################
# S-DES has two rounds and for each round we need to generate a new key. Thus we need to repeat Step 1-Step 5 two times.         #
# The following procedure encompasses all the steps of the key generation: takes as input a 10-bit master key and produces two   #
# round keys.                                                                                                                    #
##################################################################################################################################

def fullKeyGenerationSDES(masterKey):
    KeyPerm = initalPermKey(masterKey)
    splitKeyArr = splitKey(KeyPerm)
    splitKeyRotated = rotateSplitKeyBy1(splitKeyArr)
    RK1 = extractRK(splitKeyRotated)
    splitKeyRotatedSecondTime = rotateSplitKeyBy2(splitKeyRotated)
    RK2 = extractRK(splitKeyRotatedSecondTime)
    RKeys = []
    RKeys.append(RK1)
    RKeys.append(RK2)
    return RKeys

##################################################################################
#                   Functions for S-DES Encryption                               #
##################################################################################

########################################################################
# Step 1: Permute the bits in the Plaintext using the follwoing table. #
# Input position  1 2 3 4 5 6 7 8                                      #
# Output position 2 6 3 1 4 8 5 7                                      #
########################################################################

def initalPermutation(plaintextIn):
    permArr = [2,6,3,1,4,8,5,7]
    permText = ""
    for i in range(len(permArr)):
        permText = permText + plaintextIn[permArr[i] - 1]
    return permText

###########################################################################
# Step 2: Divide the plaintext into two halves, left half and right half  #
###########################################################################

def splitText(permTextIn):
    textLeft = ""
    textRight = ""
    for i in range(len(permTextIn)/2):
        textLeft = textLeft + permTextIn[i]
        textRight = textRight + permTextIn[i + (len(permTextIn)/2)]
    returnArr = []
    returnArr.append(textLeft)
    returnArr.append(textRight)
    return returnArr

##############################################################################################
# Step 3. Take the right 4 bits from Step 3 and use the folowing "Expand and Permute" Table  #
# Position Number 1 2 3 4 5 6 7 8                                                            #
# Expansion       4 1 2 3 2 3 4 1                                                                  #
##############################################################################################


def expandAndPermute(rightIn):#Encryption Step 4
    expandArr = [4,1,2,3,2,3,4,1]
    outText = ""
    for i in range(len(expandArr)):
        outText = outText + rightIn[(expandArr[i])-1]
    return outText


##################################################################################################
# The funcion XOROpp takes two bit strings and produces XOR opperation of the string values      #
##################################################################################################

def XOROpp(in1, in2):
    outputTxt = ""
    for i in range(len(in1)):
        if(in1[i] == in2[i]):
            outputTxt = outputTxt + "0"
        else:
            outputTxt = outputTxt + "1"
    return outputTxt

#############################################################################
# These are the S-Box look up tables used in this simplified version of DES #
#############################################################################

SBox1 = [ ["01", "00", "11", "10"], ["11", "10", "01", "00"], ["00", "10", "01", "11"], ["11", "01", "11", "10"]]
SBox2 = [ ["00", "01", "10", "11"], ["10", "00", "01", "11"], ["11", "00", "01", "00"], ["10", "01", "00", "11"]]

#####################################################################################
# Step 4: Take a 4-bit value and partition the bits into two 2 bit values denoting  #
# which rows/columns to be used in the S-Box functions                              #
#####################################################################################

def FourBitToRowCol(inNum):
    rowStr = inNum[0] + inNum[3]
    colStr = inNum[1] + inNum[2]
    rowInt = int(rowStr,2)
    colInt = int(colStr,2)
    returnArr = [rowInt,colInt]
    return returnArr

##################################################################################
# Step 5: Merge both 2-bit outputs of the S-Box layer into one 4-bit output      #
##################################################################################

def MergeSBoxOutputs(in1, in2):
    returnStr = ""
    returnStr = returnStr + in1
    returnStr = returnStr + in2
    return returnStr

#####################################################################################################
# The function ApplySBox combines Steps 4 & 5: Takes an 8-bit input and computes the S-Box layer    #
#                                                                                                   #
#####################################################################################################

def ApplySBox(textIn):
    afterSplit = splitText(textIn)
    leftIndices = FourBitToRowCol(afterSplit[0])
    rightIndices = FourBitToRowCol(afterSplit[1])
    SBox1Out = SBox1[leftIndices[0]][leftIndices[1]]
    SBox2Out = SBox2[rightIndices[0]][rightIndices[1]]
    returnText = SBox1Out + SBox2Out
    return returnText

##############################################################################################
# Step 6: Take a 4-bit input and perumtes the bits using the table                           #
# Input position  1 2 3 4                                                                    #
# Output position 2 4 3 1                                                                    #
##############################################################################################

def PermAfterSBox(inputStr):
    permArr = [2,4,3,1]
    returnStr = ""
    for i in range(len(permArr)):
        returnStr = returnStr + inputStr[permArr[i]-1]
    return returnStr

#################################################################################
# The function MergeTwo4Bits merges two 4-bit strings into one string           #
#################################################################################
def MergeTwo4Bits(inLeft, inRight):
    returnStr = inLeft + inRight
    return returnStr

#################################################################################
# The function SwapPair swaps two 4-bit strings                                 #
#################################################################################

def SwapPair(inputArr):
    returnArr = []
    returnArr.append(inputArr[1])
    returnArr.append(inputArr[0])
    return returnArr
#######################################################################################
# Step 14: Takes as input an 8 -bit number and preformes the Final Permutation        #
# Input Position  1 2 3 4 5 6 7 8                                                     #
# Output Position 4 1 3 5 7 2 8 6                                                     #
#######################################################################################

def FinalPermutation(inStr):#In Step 14
    PermArr = [4,1,3,5,7,2,8,6]
    returnStr = ""
    for i in range(len(PermArr)):
        returnStr = returnStr + inStr[PermArr[i]-1]
    return returnStr

###############################################################################################
# One Round of SDES                                                                           #
# Takes as input text state and computes a full round of SDES                                 #
# Note it is assumed that Inital/Final Permutations are executed outside of this function     #
# This funcion outputs a text state in which one round of encryptinon has been preformed on it#
###############################################################################################
def OneRoundSDES(textState, RoundKey):
    splitPermText = splitText(textState) #Step 3
    expandedRight = expandAndPermute(splitPermText[1])#Step 4
    afterFirstXOR = XOROpp(expandedRight,RoundKey) #Step 5
    splitAfterXOR = splitText(afterFirstXOR)#Step6
    leftSBoxIn = FourBitToRowCol(splitAfterXOR[0])#Step6
    rightSBoxIn = FourBitToRowCol(splitAfterXOR[1])#Step6
    SBox1Out = SBox1[leftSBoxIn[0]][leftSBoxIn[1]]#Step6
    SBox2Out = SBox2[rightSBoxIn[0]][rightSBoxIn[1]]#Step6
    SBoxOutFull = MergeSBoxOutputs(SBox1Out, SBox2Out)#Step7
    permAfterSBox = PermAfterSBox(SBoxOutFull)#Step8
    step9XOR = XOROpp(splitPermText[0] , permAfterSBox)#Step9
    Step10Merge = MergeTwo4Bits(step9XOR,splitPermText[1])#Step10
    Step11Split = splitText(Step10Merge)#Step11
    Step12Swap = SwapPair(Step11Split)#Step12
    Step12Merge = MergeTwo4Bits(Step12Swap[0],Step12Swap[1])#Step12
    return Step12Merge



#################################################################################################################################################
# The function SDESFullEncryption takes as input a 10-bit key and an 8-bit Plaintext and computes the ciphertext (note that SDES has two rounds)#                    #
#################################################################################################################################################

def SDESFullEncryption(Plaintext, Key):
    RoundKeys = fullKeyGenerationSDES(Key)
    textState = initalPermutation(Plaintext)
    #print("State after inital permutation" , textState)
    for i in range(len(RoundKeys)):
        textState = OneRoundSDES(textState, RoundKeys[i])
        #print("After round", i, "The textState is" , textState)#Prints out status after each round if uncommented
    Step14Split = splitText(textState)
    Step14Swap = SwapPair(Step14Split)
    Step14Merge = MergeTwo4Bits(Step14Swap[0],Step14Swap[1])
    #print("Before Final permutation the state is" , Step14Merge)
    Ciphertext = FinalPermutation(Step14Merge)
    return Ciphertext


#################################################################################################################################################
# The function SDESFullDecryption takes in as input a 10-bit key and 8-bit Ciphertext and recovers the plaintext (note that SDES has two rounds)#
# Note the decryption is the same as the encryption but the round keys are applied in reverser order                                            #
#################################################################################################################################################
def SDESFullDecryption(Ciphertext, Key):
    RoundKeys = fullKeyGenerationSDES(Key)
    textState = initalPermutation(Ciphertext)
    #print("after inital permutation the state is" , textState)
    for i in range(len(RoundKeys)):
        textState = OneRoundSDES(textState, RoundKeys[len(RoundKeys)-1-i])
        #print("After round", i, "The textState is" , textState)
    Step14Split = splitText(textState)
    Step14Swap = SwapPair(Step14Split)
    Step14Merge = MergeTwo4Bits(Step14Swap[0],Step14Swap[1])
    #print("Before Final permutation the state is" , Step14Merge)
    Plaintext = FinalPermutation(Step14Merge)
    return Plaintext

########################################################################
# Example. Step-by-Step key generation                                 #
########################################################################

Key = "1010000010"
print("Key ", Key ," Chosen (Key Generation Step 1)")

KeyOut = initalPermKey(Key)
print("Produces Inital Permutation of Key", KeyOut, "(Key Generation Step 2)")

splitKeyArr = splitKey(KeyOut)
print("Split Key into sub-keys", splitKeyArr, "(Key Generation Step 3)")

splitKeyRotated = rotateSplitKeyBy1(splitKeyArr)
print("After Rotation by 1-bit" , splitKeyRotated, "(Key Generation Step 4)")

RK1 = extractRK(splitKeyRotated)
print("Produced First Round Key RK1:" , RK1, "(Key Generation Step 5)")

splitKeyRotatedSecondTime = rotateSplitKeyBy2(splitKeyRotated)
print("After Rotation by 2-bits" , splitKeyRotatedSecondTime, "(Key Generation Step 6-7)")

RK2 = extractRK(splitKeyRotatedSecondTime)
print("Produces Second Round Key RK2:" , RK2, "(Key Generation Step 8)")

########################################################################
# Example. S-DES Key Generation                                        #
########################################################################
Key = "1010000010"
RKeys = fullKeyGenerationSDES(Key)
print("From Key" , Key, "The SDES key generator produces the following Round Keys\n", RKeys)

########################################################################
# Example. S-DES Steo-by-Step encryption                               #
########################################################################

Key = "1010000010"
RKeys = fullKeyGenerationSDES(Key)
print("Round Keys" , RKeys)
M = "01110010"

permText = initalPermutation(M)
print("Preformed Inital Permutation of Plaintext (Encryption Step 2)" , permText)

splitPermText = splitText(permText)
print("Split Text (Encryption Step 3)" , splitPermText)

expandedRight = expandAndPermute(splitPermText[1])
print("Expanded Right (Encryption Step 4)", expandedRight)

afterFirstXOR = XOROpp(expandedRight,RKeys[0])
print("After XOR Opperation (Encryption Step 5)" , afterFirstXOR)

print("begenning S-Box Layer (Encryption Step 6)")
splitAfterXOR = splitText(afterFirstXOR)
leftSBoxIn = FourBitToRowCol(splitAfterXOR[0])
rightSBoxIn = FourBitToRowCol(splitAfterXOR[1])
print("SBox1 Inputs", leftSBoxIn, "    SBox2 Inptus" , rightSBoxIn)

SBox1Out = SBox1[leftSBoxIn[0]][leftSBoxIn[1]]
print ("SBox1 Output" , SBox1Out)

SBox2Out = SBox2[rightSBoxIn[0]][rightSBoxIn[1]]
print ("SBox2 Output" , SBox2Out)
print("(Encryption Step 6) Complete")

SBoxOutFull = MergeSBoxOutputs(SBox1Out, SBox2Out)
print("SBox Out After Merge (Encryption Step 7)" , SBoxOutFull)

permAfterSBox = PermAfterSBox(SBoxOutFull)
print("After Permutation After SBox (Encryption Step 8)" , permAfterSBox)
print("Left Value From Step 3" , splitPermText[0])

step9XOR = XOROpp(splitPermText[0] , permAfterSBox)
print("XOR Output (Encryption Step 9)" , step9XOR)
print("Right Value From Step 3" , splitPermText[1])

Step10Merge = MergeTwo4Bits(step9XOR,splitPermText[1])
print("Merge Value (Encryption Step 10)" , Step10Merge)

Step11Split = splitText(Step10Merge)
print("Split Text (Encryption Step 11)", Step11Split)

Step12Swap = SwapPair(Step11Split)
Step12Merge = MergeTwo4Bits(Step12Swap[0],Step12Swap[1])
print("After Swap and Merge (Encryption Step 12)" , Step12Merge)

print("Completed 1 round with a textState Value of " , Step12Merge, "\n\n")
print("Starting 2nd round of encryption")

splitPermText = splitText(Step12Merge)
print("Split Text (Encryption Step 3)" , splitPermText)

expandedRight = expandAndPermute(splitPermText[1])
print("Expanded Right (Encryption Step 4)", expandedRight)

afterFirstXOR = XOROpp(expandedRight,RKeys[1])
print("After XOR Opperation (Encryption Step 5)" , afterFirstXOR)

print("begenning S-Box Layer (Encryption Step 6)")
splitAfterXOR = splitText(afterFirstXOR)
leftSBoxIn = FourBitToRowCol(splitAfterXOR[0])
rightSBoxIn = FourBitToRowCol(splitAfterXOR[1])
print("SBox1 Inputs", leftSBoxIn, "    SBox2 Inptus" , rightSBoxIn)

SBox1Out = SBox1[leftSBoxIn[0]][leftSBoxIn[1]]
print ("SBox1 Output" , SBox1Out)

SBox2Out = SBox2[rightSBoxIn[0]][rightSBoxIn[1]]
print ("SBox2 Output" , SBox2Out)
print("(Encryption Step 6) Complete")

SBoxOutFull = MergeSBoxOutputs(SBox1Out, SBox2Out)
print("SBox Out After Merge (Encryption Step 7)" , SBoxOutFull)

permAfterSBox = PermAfterSBox(SBoxOutFull)
print("After Permutation After SBox (Encryption Step 8)" , permAfterSBox)
print("Left Value From Step 3" , splitPermText[0])

step9XOR = XOROpp(splitPermText[0] , permAfterSBox)
print("XOR Output (Encryption Step 9)" , step9XOR)
print("Right Value From Step 3" , splitPermText[1])

Step10Merge = MergeTwo4Bits(step9XOR,splitPermText[1])
print("Merge Value (Encryption Step 10)" , Step10Merge)

Step11Split = splitText(Step10Merge)
print("Split Text (Encryption Step 11)", Step11Split)

Step12Swap = SwapPair(Step11Split)
Step12Merge = MergeTwo4Bits(Step12Swap[0],Step12Swap[1])
print("After Swap and Merge (Encryption Step 12)" , Step12Merge)

print("Finished second round of encryption with a textstate value of" , Step12Merge, "\n\n")


print("Begenning (Encryption Step 14)")
Step14Split = splitText(Step13RK2XOR)
Step14Swap = SwapPair(Step14Split)
Step14Merge = MergeTwo4Bits(Step14Swap[0],Step14Swap[1])
print("Swap and Merge Result", Step14Merge)


CipherText = FinalPermutation(Step14Merge)
print("Ciphertext: " , CipherText)
print("Encryption Complete")

#################################################################################################
# Example. S-DES encryption of the Plaintext = "01110010"  using the Key = "1010000010"         #
#################################################################################################

Key = "1010000010"
Plaintext = "01110010"
Ciphertext = SDESFullEncryption(Plaintext, Key)
print("Using Key:", Key, "\nand Plaintext:", Plaintext, "\nThe SDES Cryptographic Primitive Produces \nCiphertext:", Ciphertext)

Key = "1010000010"
Ciphertext = "01110111"
recoveredPlaintext = SDESFullDecryption(Ciphertext, Key)
print("Using Key:", Key, "\nand Ciphertext:", Ciphertext, "\nThe SDES Cryptographic Primitive Produces \nPlaintext:", recoveredPlaintext)

#########################################
# Second Example Full SDES              #
#########################################

Key = "0101101111"
print("Key: ", Key)
Plaintext = "11010101"
print("Plaintext: ", Plaintext)
Ciphertext = SDESFullEncryption(Plaintext, Key)
print("Ciphertext: ", Ciphertext)
RecoveredPlaintext = SDESFullDecryption(Ciphertext, Key)
print("Recovered Plaintext: ", RecoveredPlaintext)