椭圆曲线密码算法一

一、关于椭圆曲线密码算法中点加、点乘的例子

As an example of the encryption process (taken from [KOBL94]), take p=751, Ep(1,188), which is equivalent to the curve y2=x3-x+188; and G=(0,376). Suppose the A wishes to send a message to B that is encoded in the elliptic point Pm=(562,201) and that A selects the random number k=386. B’s public key is Pb=(201,5). We have 386(0,376)=(676,558), and (562,201)+386(201,5)=(385,328). Thus, A sends the cipher text {(676,558), (385,328}.

 

 1、计算386(0,376)

 386(0,376)

=(256 + 128 + 2)(0,376)

=256(0,376) + 128(0,376) + 2(0,376)

1) 2(0,376)即为2G

相同点相加,故

t = (3xp+ a)/(2yp) (mod p)

=(3 x 02 - 1)/(2 x 376) (mod p)

=-752-1 (mod p)

因1 x 752 = 1 mod p,故752-1 = 1

=-1 (mod p)

= p - 1

= 751 - 1

= 750

2G=(0,376)+(0,376)

=(7502 - 0 - 0 (mod p), 750(0 - xr) - 376 (mod p))

=(1, -750-376 (mod p))

=(1, -375 (mod p))

=(1, p - 375)

=(1, 376) // 2G

 

2) 4G = 2(2G) = (1,376) + (1,376)

t = (3xp+ a)/(2yp) (mod p)

=(3 x 12 - 1)/(2 x 376) (mod p)

=376-1 (mod p)

因2 x 376 = 1 mod p,故376-1 = 2

=2 (mod p)

=2

4G=(1,376)+(1,376)

=(22 - 1 - 1 (mod p), 2(1 - xr) - 376 (mod p))

=(2, -378 (mod p))

=(2, p - 378)

=(2, 373) // 4G

 

3) 8G = 2(4G) = (2,373) + (2,373)

t = (3xp+ a)/(2yp) (mod p)

=(3 x 22 - 1)/(2 x 373) (mod p)

=11 x 746-1 (mod p)

因150 x 746 = 1 mod p,故746-1 = 150

=11 x 150 (mod p)

=148

8G=(2,373) + (2,373)

=(1482 - 2 - 2 (mod p), 148(2 - xr) - 373 (mod p))

=(121, -148 x 119 - 373 (mod p))

=(121, -712 (mod p))

=(121, p - 712)

=(121, 39) // 8G

 

4) 16G = 2(8G) = (121,39) + (121,39)

t = (3xp+ a)/(2yp) (mod p)

=(3 x 1212 - 1)/(2 x 39) (mod p)

=364 x 78-1 (mod p)

因337 x 78 = 1 mod p,故78-1 = 337

=364 x 337 (mod p)

=255

16G=(121,39) + (121,39)

=(2552 - 121 - 121 (mod p), 255(121 - xr) - 39 (mod p))

=(197, 255 x (-76) - 39 (mod p))

=(197, -19419 (mod p))

=(197, -644 (mod p))

=(197, p - 644)

=(197, 107) // 16G

 

5) 32G = 2(16G) = (197,107) + (197,107)

t = (3xp+ a)/(2yp) (mod p)

=(3 x 1972 - 1)/(2 x 107) (mod p)

=21 x 214-1 (mod p)

因186 x 214 = 1 mod p,故214-1 = 186

=21 x 186 (mod p)

=151

32G=(197,107) + (197,107)

=(1512 - 197 - 197 (mod p), 151(197 - xr) - 107 (mod p))

=(628, -602 (mod p))

=(628, p - 602)

=(628, 149) // 32G

 

6) 64G = 2(32G) = (628,149) + (628,149) 

t = (3xp+ a)/(2yp) (mod p)

=(3 x 6282 - 1)/(2 x 149) (mod p)

=326 x 298-1 (mod p)

因688 x 298 = 1 mod p,故298-1 = 688

=326 x 688 (mod p)

=490

64G= (628, 149) + (628, 149) 

=(4902 - 628 - 628 (mod p), 490(628 - xr) - 149 (mod p))

=(26, 439) // 64G

 

7) 128G = 2(64G) = (26,439) + (26,439

t = (3xp+ a)/(2yp) (mod p)

=(3 x 262 - 1)/(2 x 439) (mod p)

=525 x 127-1 (mod p)

因615 x 127 = 1 mod p,故127-1 = 615

=525 x 615 (mod p)

=696

128G= (26, 439) + (26, 439) 

=(6962 - 2- 2(mod p), 696(26 - xr) - 439 (mod p))

=(720,-570 (mod p))

=(720, 181) // 128G

 

8) 256G = 2(128G) = (720,181) + (720,181

t = (3xp+ a)/(2yp) (mod p)

=(3 x 7202 - 1)/(2 x 181) (mod p)

=629 x 362-1 (mod p)

因139 x 362 = 1 mod p,故362-1 = 139

=629 x 139 (mod p)

=315

256G= (720,181) + (720,181

=(3152 - 720 - 720 (mod p), 315(720 - xr) - 181 (mod p))

=(155,558) // 256G

 

2、计算386(0,376)

386(0,376) =256(0,376) + 128(0,376) + 2(0,376)

386(0,376) =(155,558) + (720, 181) + (1, 376)

因 P != Q,故 t = (y- yP) / (x- xP) (mod p)

t =(181 - 558)/(720 - 155) (mod p)

t =-377 x 565-1 (mod p)

因537 x 565 = 1 (mod p),故565-1 = 537

t =-377 x 537 (mod p)

t =-430 (mod p)

t =p - 430

t =321

386(0,376) =(155,558) + (720, 181) + (1, 376)

386(0,376) =(3212 - 155 - 720, 321(155 - xr) - 558) (mod p) + (1,376) (mod p)

386(0,376) =(30, 515) + (1, 376) (mod p)

 

再因 P != Q,故 t = (y- yP) / (x- xP) (mod p)

t =(376 - 515) / (1 - 30) (mod p)

t =(-139) / (-29) (mod p)

t = 139 x 29 -1 (mod p)

因259 x 29 = 1 (mod p),故29-1 = 259

t = 139 x 259 (mod p)

t =704 (mod p)

t =704

386(0,376) =(30, 515) + (1, 376) (mod p)

386(0,376) =(7042 - 30 - 1, 704(30 - xr) - 515) (mod p)

386(0,376) =(676, -193) (mod p)

386(0,376) =(676, 558) (mod p)

 

3、一个求逆的简单程序

#include <stdio.h>

int main(void)
{
    int i;
    int value = 29;
    
    for (i = 1; i < 751; ++i) {
        if (i * value % 751 == 1) {
            printf("iv value of [%d] is [%d]\n", value, i);
            break;
        }
    }
    
    if (i == 751) {
        printf("no value\n");
    }
    return 0;
}

 

【参考文献】

 

上一篇:[力扣每日一题]376. 摆动序列


下一篇:C语言重构【376】 摆动序列