| Hosted by CoCalc | Download
n = var('n')
l = var('l')
lp = var('lp')
k = var('k')
kappa = var('kappa')
s = var('s')
t = var('t')
d = var('d')
r = var('r')

Step1 = n / 2
Step2 = t
Step3 = n / 2
Step4 = lp
Step5 = n - l
Step6 = r + n - t

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

pairs1 = 2 * r
pairs2 = k * n - (k + 1) * d
pairs_eq = (pairs1 == pairs2)
show('--------------------------------------------------------------------')
show('When the message length is limited to be no more than (log2): ', n / 2)
show('the success of the attack requires: ', pairs_eq)
rs = solve([pairs_eq], r)[0]
show('which implies: ', rs)
rs = rs.rhs()

Step6 = Step6(r = rs)
show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())

ts = solve([Step2 == Step6], t)[0]
show('--------------------------------------------------------------------')
show('Balance the Step 2 and 6 by setting: ')
show(ts)
ts = ts.rhs()

Step2  = Step2(t = ts)
Step6  = Step6(t = ts)

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())

show('--------------------------------------------------------------------')
show('Optimize the complexity by setting: ')
show(d == n/2)
show(lp == n/2)
Step2  = Step2(d = n/2, lp = n/2)
Step4  = Step4(lp = n/2)
Step6  = Step6(d = n/2, lp = n/2)

show('--------------------------------------------------------------------')
show('Complexity of Phases are (log2): ')
show('Step 1: ', Step1.simplify_full())
show('Step 2: ', Step2.simplify_full())
show('Step 3: ', Step3.simplify_full())
show('Step 4: ', Step4.simplify_full())
show('Step 5: ', Step5.simplify_full())
show('Step 6: ', Step6.simplify_full())
show('--------------------------------------------------------------------')

for i in range(2, 6):
    show(' ------------------------------ ', k == i, ' ------------------------------')
    Step2cplx = Step2(k = i)
    Step2cplxs = Step2cplx(kappa=log(i, 2)).simplify_full()
    show('Complexity is: ', Step2cplxs)
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: 12 n\displaystyle \frac{1}{2} \, n
Step 2: t\displaystyle t
Step 3: 12 n\displaystyle \frac{1}{2} \, n
Step 4: lp\displaystyle \mathit{lp}
Step 5: −l+n\displaystyle -l + n
Step 6: n+r−t\displaystyle n + r - t
--------------------------------------------------------------------
--------------------------------------------------------------------
When the message length is limited to be no more than (log2): 12 n\displaystyle \frac{1}{2} \, n
the success of the attack requires: 2 r=−d(k+1)+kn\displaystyle 2 \, r = -d {\left(k + 1\right)} + k n
which implies: r=−12 dk+12 kn−12 d\displaystyle r = -\frac{1}{2} \, d k + \frac{1}{2} \, k n - \frac{1}{2} \, d
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: 12 n\displaystyle \frac{1}{2} \, n
Step 2: t\displaystyle t
Step 3: 12 n\displaystyle \frac{1}{2} \, n
Step 4: lp\displaystyle \mathit{lp}
Step 5: −l+n\displaystyle -l + n
Step 6: −12 dk+12 (k+2)n−12 d−t\displaystyle -\frac{1}{2} \, d k + \frac{1}{2} \, {\left(k + 2\right)} n - \frac{1}{2} \, d - t
--------------------------------------------------------------------
Balance the Step 2 and 6 by setting:
t=−14 dk+14 (k+2)n−14 d\displaystyle t = -\frac{1}{4} \, d k + \frac{1}{4} \, {\left(k + 2\right)} n - \frac{1}{4} \, d
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: 12 n\displaystyle \frac{1}{2} \, n
Step 2: −14 dk+14 (k+2)n−14 d\displaystyle -\frac{1}{4} \, d k + \frac{1}{4} \, {\left(k + 2\right)} n - \frac{1}{4} \, d
Step 3: 12 n\displaystyle \frac{1}{2} \, n
Step 4: lp\displaystyle \mathit{lp}
Step 5: −l+n\displaystyle -l + n
Step 6: −14 dk+14 (k+2)n−14 d\displaystyle -\frac{1}{4} \, d k + \frac{1}{4} \, {\left(k + 2\right)} n - \frac{1}{4} \, d
--------------------------------------------------------------------
Optimize the complexity by setting:
d=12 n\displaystyle d = \frac{1}{2} \, n
lp=12 n\displaystyle \mathit{lp} = \frac{1}{2} \, n
--------------------------------------------------------------------
Complexity of Phases are (log2):
Step 1: 12 n\displaystyle \frac{1}{2} \, n
Step 2: 18 (k+3)n\displaystyle \frac{1}{8} \, {\left(k + 3\right)} n
Step 3: 12 n\displaystyle \frac{1}{2} \, n
Step 4: 12 n\displaystyle \frac{1}{2} \, n
Step 5: −l+n\displaystyle -l + n
Step 6: 18 (k+3)n\displaystyle \frac{1}{8} \, {\left(k + 3\right)} n
--------------------------------------------------------------------
------------------------------ k=2\displaystyle k = 2 ------------------------------
Complexity is: 58 n\displaystyle \frac{5}{8} \, n
------------------------------ k=3\displaystyle k = 3 ------------------------------
Complexity is: 34 n\displaystyle \frac{3}{4} \, n
------------------------------ k=4\displaystyle k = 4 ------------------------------
Complexity is: 78 n\displaystyle \frac{7}{8} \, n
------------------------------ k=5\displaystyle k = 5 ------------------------------
Complexity is: n\displaystyle n
------------------------------ k=3\displaystyle k = 3 ------------------------------
Complexity is: 34 n\displaystyle \frac{3}{4} \, n
------------------------------ k=4\displaystyle k = 4 ------------------------------
Complexity is: 78 n\displaystyle \frac{7}{8} \, n
------------------------------ k=5\displaystyle k = 5 ------------------------------
Complexity is: n\displaystyle n