CoCalc -- Continued fraction low exponent attack.sagews

Project: Math 485 Fall 2015

Path: Continued fraction low exponent attack.sagews

Views: ²⁵⁶

#Function definitions - make sure to evaluate this block first

ntt = {0: ' ', 1: '!', 2: '"', 3: '#', 4: '$', 5: '%', 6: '&', 7: "'", 8: '(', 9: ')', 10: '*', 11: '+', 12: ',', 13: '-', 14: '.', 15: '/', 16: '0', 17: '1', 18: '2', 19: '3', 20: '4', 21: '5', 22: '6', 23: '7', 24: '8', 25: '9', 26: ':', 27: ';', 28: '<', 29: '=', 30: '>', 31: '?', 32: '@', 33: 'A', 34: 'B', 35: 'C', 36: 'D', 37: 'E', 38: 'F', 39: 'G', 40: 'H', 41: 'I', 42: 'J', 43: 'K', 44: 'L', 45: 'M', 46: 'N', 47: 'O', 48: 'P', 49: 'Q', 50: 'R', 51: 'S', 52: 'T', 53: 'U', 54: 'V', 55: 'W', 56: 'X', 57: 'Y', 58: 'Z', 59: '[', 60: '\\', 61: ']', 62: '^', 63: '_', 64: '`', 65: 'a', 66: 'b', 67: 'c', 68: 'd', 69: 'e', 70: 'f', 71: 'g', 72: 'h', 73: 'i', 74: 'j', 75: 'k', 76: 'l', 77: 'm', 78: 'n', 79: 'o', 80: 'p', 81: 'q', 82: 'r', 83: 's', 84: 't', 85: 'u', 86: 'v', 87: 'w', 88: 'x', 89: 'y', 90: 'z', 91: '{', 92: '|', 93: '}', 94: '~', 95: '¢', 96: '£', 97: '«', 98: '»', 99: '±'}

ttn = dict((v,k) for k, v in ntt.iteritems())

def text_to_num(text):
    num = 0
    for i in range(len(text)):
        num *= 100
        num += ttn[text[i]]
    return num

def num_to_text(num):
    text = ''
    while num > 0:
        cha = (num%100)
        text = ntt[cha] + text
        num = (num-cha)/100
    return text

Error in lines 2-2
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1234, in execute
    flags=compile_flags), namespace, locals)
  File "", line 1, in <module>
AttributeError: 'dict' object has no attribute 'iteritems'

e=1560351375878635729085960250567

1560351375878635729085960250567

n=1785419685384046795688039868187

1785419685384046795688039868187

c=68665421420582238773570911029

68665421420582238773570911029

continued_fraction(e/n, 100)

[0; 1, 6, 1, 13, 1, 7, 4, 50219219, 1, 4, 1, 4, 1239, 1, 2, 5, 1, 9, 2, 1, 1, 1, 1, 1, 12, 1, 1, 1, 10, 3, 4, 1, 14, 1, 2, 1, 11, 4, 1, 1, 62, 1, 1, 1, 1, 1, 2]

continued_fraction(e/n, 100).convergents()

[0, 1, 6/7, 7/8, 97/111, 104/119, 825/944, 3404/3895, 170946222301/195603858949, 170946225705/195603862844, 854731125121/978019310325, 1025677350826/1173623173169, 4957440528425/5672512003001, 6143294492069401/7029415994891408, 6148251932597826/7035088506894409, 18439798357265053/21099593008680226, 98347243718923091/112533053550295539, 116787042076188144/133632646558975765, 1149430622404616387/1315226872581077424, 2415648286885420918/2764086391721130613, 3565078909290037305/4079313264302208037, 5980727196175458223/6843399656023338650, 9545806105465495528/10922712920325546687, 15526533301640953751/17766112576348885337, 25072339407106449279/28688825496674432024, 316394606186918345099/362032018536442069625, 341466945594024794378/390720844033116501649, 657861551780943139477/752752862569558571274, 999328497374967933855/1143473706602675072923, 10651146525530622478027/12187489928596309300504, 32952768073966835367936/37705943492391602974435, 142462218821397963949771/163011263898162721198244, 175414986895364799317707/200717207390554324172679, 2598272035356505154397669/2973052167365923259615750, 2773687022251869953715376/3173769374756477583788429, 8145646079860245061828421/9320590916878878427192608, 10919333102112115015543797/12494360291635356010981037, 128258310203093510232810188/146758554124867794547984015, 523952573914486155946784549/599528576791106534202917097, 652210884117579666179594737/746287130915974328750901112, 1176163458032065822126379286/1345815707707080862953818209, 73574345282105660638015110469/84186861008754987831887630070, 74750508740137726460141489755/85532676716462068694841448279, 148324854022243387098156600224/169719537725217056526729078349, 223075362762381113558298089979/255252214441679125221570526628, 371400216784624500656454690203/424971752166896181748299604977, 594475579547005614214752780182/680223966608575306969870131605, 1560351375878635729085960250567/1785419685384046795688039868187]

#Remember that we think that one of the convergents is k/d, and our C is (e*d-1)/k.
C1=(e*1-1)/1

C1

1560351375878635729085960250566

solve(x^2-(n-C1+1)*x+n, x)

[x == -sqrt(12663935985905877368868304269952590683844622219275393365534) + 112534154752705533301039808811, x == sqrt(12663935985905877368868304269952590683844622219275393365534) + 112534154752705533301039808811]

C3=(e*8-1)/7

C3

12482811007029085832687682004535/7

C5=(e*119-1)/104

C5

23210226716194706470153658727184/13

C7=(e*3895-1)/3404

C7

1785419685384044114215574376016

solve(x^2 - (n-C7+1)*x+n, x)

[x == 1450981234510883, x == 1230491230981289]

d=pow(e, -1, (1450981234510883-1)*(1230491230981289-1))

3895

pow(c, d, n)

55827978710065788387698214

num_to_text(55827978710065788387698214)

'Wrong answer.'

e/n

1560351375878635729085960250567/1785419685384046795688039868187

#Function definitions - make sure to evaluate this block first

ntt = {0: ' ', 1: '!', 2: '"', 3: '#', 4: '$', 5: '%', 6: '&', 7: "'", 8: '(', 9: ')', 10: '*', 11: '+', 12: ',', 13: '-', 14: '.', 15: '/', 16: '0', 17: '1', 18: '2', 19: '3', 20: '4', 21: '5', 22: '6', 23: '7', 24: '8', 25: '9', 26: ':', 27: ';', 28: '<', 29: '=', 30: '>', 31: '?', 32: '@', 33: 'A', 34: 'B', 35: 'C', 36: 'D', 37: 'E', 38: 'F', 39: 'G', 40: 'H', 41: 'I', 42: 'J', 43: 'K', 44: 'L', 45: 'M', 46: 'N', 47: 'O', 48: 'P', 49: 'Q', 50: 'R', 51: 'S', 52: 'T', 53: 'U', 54: 'V', 55: 'W', 56: 'X', 57: 'Y', 58: 'Z', 59: '[', 60: '\\', 61: ']', 62: '^', 63: '_', 64: '`', 65: 'a', 66: 'b', 67: 'c', 68: 'd', 69: 'e', 70: 'f', 71: 'g', 72: 'h', 73: 'i', 74: 'j', 75: 'k', 76: 'l', 77: 'm', 78: 'n', 79: 'o', 80: 'p', 81: 'q', 82: 'r', 83: 's', 84: 't', 85: 'u', 86: 'v', 87: 'w', 88: 'x', 89: 'y', 90: 'z', 91: '{', 92: '|', 93: '}', 94: '~', 95: '¢', 96: '£', 97: '«', 98: '»', 99: '±'}

ttn = dict((v,k) for k, v in ntt.iteritems())

def text_to_num(text):
    num = 0
    for i in range(len(text)):
        num *= 100
        num += ttn[text[i]]
    return num

def num_to_text(num):
    text = ''
    while num > 0:
        cha = (num%100)
        text = ntt[cha] + text
        num = (num-cha)/100
    return text

e=1560351375878635729085960250567

1560351375878635729085960250567

n=1785419685384046795688039868187

1785419685384046795688039868187

c=68665421420582238773570911029

68665421420582238773570911029

continued_fraction(e/n, 100)

[0; 1, 6, 1, 13, 1, 7, 4, 50219219, 1, 4, 1, 4, 1239, 1, 2, 5, 1, 9, 2, 1, 1, 1, 1, 1, 12, 1, 1, 1, 10, 3, 4, 1, 14, 1, 2, 1, 11, 4, 1, 1, 62, 1, 1, 1, 1, 1, 2]

continued_fraction(e/n, 100).convergents()

[0, 1, 6/7, 7/8, 97/111, 104/119, 825/944, 3404/3895, 170946222301/195603858949, 170946225705/195603862844, 854731125121/978019310325, 1025677350826/1173623173169, 4957440528425/5672512003001, 6143294492069401/7029415994891408, 6148251932597826/7035088506894409, 18439798357265053/21099593008680226, 98347243718923091/112533053550295539, 116787042076188144/133632646558975765, 1149430622404616387/1315226872581077424, 2415648286885420918/2764086391721130613, 3565078909290037305/4079313264302208037, 5980727196175458223/6843399656023338650, 9545806105465495528/10922712920325546687, 15526533301640953751/17766112576348885337, 25072339407106449279/28688825496674432024, 316394606186918345099/362032018536442069625, 341466945594024794378/390720844033116501649, 657861551780943139477/752752862569558571274, 999328497374967933855/1143473706602675072923, 10651146525530622478027/12187489928596309300504, 32952768073966835367936/37705943492391602974435, 142462218821397963949771/163011263898162721198244, 175414986895364799317707/200717207390554324172679, 2598272035356505154397669/2973052167365923259615750, 2773687022251869953715376/3173769374756477583788429, 8145646079860245061828421/9320590916878878427192608, 10919333102112115015543797/12494360291635356010981037, 128258310203093510232810188/146758554124867794547984015, 523952573914486155946784549/599528576791106534202917097, 652210884117579666179594737/746287130915974328750901112, 1176163458032065822126379286/1345815707707080862953818209, 73574345282105660638015110469/84186861008754987831887630070, 74750508740137726460141489755/85532676716462068694841448279, 148324854022243387098156600224/169719537725217056526729078349, 223075362762381113558298089979/255252214441679125221570526628, 371400216784624500656454690203/424971752166896181748299604977, 594475579547005614214752780182/680223966608575306969870131605, 1560351375878635729085960250567/1785419685384046795688039868187]

#Remember that we think that one of the convergents is k/d, and our C is (e*d-1)/k.
C1=(e*1-1)/1

C1

1560351375878635729085960250566

solve(x^2-(n-C1+1)*x+n, x)

[x == -sqrt(12663935985905877368868304269952590683844622219275393365534) + 112534154752705533301039808811, x == sqrt(12663935985905877368868304269952590683844622219275393365534) + 112534154752705533301039808811]

C3=(e*8-1)/7

C3

12482811007029085832687682004535/7

C5=(e*119-1)/104

C5

23210226716194706470153658727184/13

C7=(e*3895-1)/3404

C7

1785419685384044114215574376016

solve(x^2 - (n-C7+1)*x+n, x)

[x == 1450981234510883, x == 1230491230981289]

d=pow(e, -1, (1450981234510883-1)*(1230491230981289-1))

3895

pow(c, d, n)

55827978710065788387698214

num_to_text(55827978710065788387698214)

'Wrong answer.'

e/n

1560351375878635729085960250567/1785419685384046795688039868187

︠b8a5cf89-13cc-4293-83ea-e852ad99367f︠