Hi there!

Ive been looking to get some help on a small script im writing to recover an encrypted word for homework.
Its a 5 character word of random capital letters encrypted with the RSA algorithm.
I undesrtand that Rsa is not a block cipher.
Its been encrypted in two 24 bit blocks .
I have the public key and the decimal values of the encrypted blocks.
I have to use a dictionary as well to use a search attack to recover the word.
I had some help with the script and i was able to build the script which i understand almost fully.

e=3;n=20149273                       # public key                 
table={}                  #dictionary                                                         

first="";second=""

for lett1 in range(65,91):         # looping from AAA to ZZZ
    for lett2 in range(65,91):
        for lett3 in range(65,91):
            plaintext=chr(lett1)+chr(lett2)+chr(lett3)
            block1=(lett1<<16) + (lett2<<8) + lett3          
            ciphtext=pow(block1,e,n)        # encryption
            table[plaintext]=ciphtext          # storing plain text and
                                                            #cipher text

for letter1 in range(65,91):                # looping from AA_ to ZZ_
    for letter2 in range(65,91):
        ptext=chr(letter1)+chr(letter2)+chr(32)
        block2=(letter1<<16) + (letter2<<8) + 32
        ctext=pow(block2,e,n)           
        table[ptext]=ctext          
        
for i in table.keys():                  # forward search using dictionary
    if table[i]==18864936:
        first = i
    if table[i]==14319312:
        second = i
        
print "The word is %s%s" %(first,second)

The word is stored in two blocks so we loop from AAA to ZZZ for the first 3 letters and from AA(space) to ZZ(space) as the third character in the second block is a space thus the 32 in the block encphering which is the ASCII value for space.
The cipher and the plain text are then stored in the dictionary created and using a forward search the word is recovered.
The part im having trouble to understand is the block enciphering

block1=(lett1<<16) + (lett2<<8) + lett3
block2=(letter1<<16) + (letter2<<8) + 32

How does the block enciphering part works? why do we multiply letter 1 and 2 by 2^16 and 2^8. Is it because the block has to be 24 bits? I also understand the number 32 in the second part is the space ASCII value.

Any help is appreciated,

Thanks in advance!

Recommended Answers

All 3 Replies

You're not multiplying by 2^16 and 2^8 you're shifting by 16 and 8 bits, respectively.

By doing so (and then adding), you're able to fit the two letters into a single 16 bit block... or something like that.

By shifting letter1 16 bits to the left to make room for letters 2 and 3 and shifting letter 2 8 bits to make room for letter 3. So we have a 24 bit block with three 8 bit characters. Yep i got it. Thanks!

Why the shift is needed?

Answer:

The first integer value is shifted 16(=2*8) bits and the second 8 bits, such that when added together, it forms a 24 bit integer as shown here:
11111111................
........22222222........
................33333333
------------------------+
111111112222222233333333
Here the 1s denote the ASCII value of the first letter, the 2s of the second and the 3s of the third. The .(dot) represents leading or trailing zeroes.

Block1=(c1<<16)+(c2<<8)+c3
We need to perform the bit shifting to combine our three 8-bit characters into a single 24-bit number, with the first character (c1) being in the most significant position(bits 16-24), followed by the second(bits 8-15) and then the third characters(bits 0-7). The third character (c3) does not need shifting as it is already in the least significant position.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.