0

The cipher text is wqlizYbFyjOp95Bt.ViLWHhEBx2 N=7231645985673347207280720222548553948759779729581 e=3 d=4821097323782215625692549251331855329314609896043 where d is the private key How do i solve this?

Pkr96
  • 87
  • 1
    How was the ciphertext encoded as it includes both lower and upper case characters? Without knowing that, there is no way to figure it out without guessing that piece. $$\Large m \equiv c^d \pmod{N}$$ – Moo Apr 12 '18 at 14:45
  • 1
    @Moo it was encoded with 64 letter alphabet abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.- – Pkr96 Apr 12 '18 at 14:54
  • You need to convert those letters, special characters (like the period) and numbers to numbers such that we can use the formula above. Does $a = 01, b = 02...$ or something else using that scheme? – Moo Apr 12 '18 at 14:58
  • @Moo In numbers it comes out as 2216118255013124940156157271962478374733730272354 a=0 b=1.... -=63 – Pkr96 Apr 12 '18 at 15:01
  • See if this comes out to anything meaningful $$\Large m \equiv c^d \pmod{N} = 970076824680893648179763130080906806851394045029$$ – Moo Apr 12 '18 at 15:03
  • @Moo Nope...It's a multiple choice question and the first letters are Llan although one option is None of the above – Pkr96 Apr 12 '18 at 16:13
  • Do they provide any other additional information on how they chunked up the message - did they do it five characters at a time or something like that? Perhaps they did it in blocks instead of a giant blob? – Moo Apr 12 '18 at 16:39
  • Nope no other info..Just what i have stated above in the question – Pkr96 Apr 12 '18 at 16:46
  • It is hard to say, I would try various things to see. – Moo Apr 12 '18 at 17:34
  • How would i approach this if i didn't have the deciphering key? – Pkr96 Apr 12 '18 at 18:17
  • See the process here: https://math.stackexchange.com/questions/586263/rsa-encryption-decryption-scheme – Moo Apr 12 '18 at 18:26
  • Is the encoding like working in base-64 instead of 10, or is it some string manipulation? Examples? The problem is underspecified. – Henno Brandsma Apr 13 '18 at 08:08

2 Answers2

1

Your ciphertext was wqlizYbFyjOp95Bt.ViLWHhEBx2 using the 64-base alphabet (from the comments; it should have been part of the question!) abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.-

You can write functions to convert strings to numbers and numbers back to strings, e.g. using Python:

def toDec(c):
    alph='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.-'
    value=0
    b=1 #value of current position
    for w in reversed(list(c)):
            value += b*alph.index(w)
            b *= 64
    return value

and

def toBase(n):
    alph='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.-'
    s=''
    while n:
            s =  str(alph[n % 64]) + s
            n -= n%64
            n/=64
    return s

So your ciphertext string represents the number c=2032648950572077788772410497891338100431128212982 which is indeed $< N$ where N= 7231645985673347207280720222548553948759779729581

Decryption in RSA is exponentation by $d$ modulo $N$: $m=c^d \bmod{N}$ and this gives the number $m=49409962907892021177240969231692222477$.

Converting back to the base again to get a textual representation we get

toBase(m) = Llanbedr-Pont-Steffan

which seems to be the Welsh name for Lampeter

Henno Brandsma
  • 242,131
  • Thanks a lot for your help! How exactly did you run the Python code? – Pkr96 Apr 14 '18 at 14:12
  • @Pkr96 I put it in a file and called the Python interpreter on the command line. I always work on Unix systems (macOS or Linux mostly) so I have one available whenever I need it. It’s my go-to tool for this kind of stuff. – Henno Brandsma Apr 14 '18 at 14:16
  • I have another Q where i don't have the d value..Struggling with the Python side of the questions – Pkr96 Apr 14 '18 at 14:22
  • @Pkr96 post a new question on that then. You can solve the RSA without the $d$? – Henno Brandsma Apr 14 '18 at 14:23
  • I have posted a new question! Can you? How so? – Pkr96 Apr 14 '18 at 14:29
0

If you want to encrypt some text, then you take the message to a number $n < N$. the cypher text is then $$ c = n^e \mod N $$ To recover the plaintext you calculate $$ n = c^d \mod N $$ and then take this back to the plaintext

Tim Dikland
  • 504