goppa_code.c

一些纠错编码算法的源代码

/*

From: [e-mail] (prometheus)

this program is a compact implementation of goppa codes with parameters
m=10, t=37 for 32-bit machines. the decoding is due to nicholas
patterson, algebraic decoding of goppa codes, itit 21 (1975), 203-207.
the encoding is somewhat older. encoding takes a 654-bit message and
produces a 1024-bit message. decoding can correct up to 37 bit errors.

goppa g gfile sfile pfile mfile < gen: generates a code determined by
gen. writes code to gfile (7k), sfile (53k), pfile (4k), mfile (82k).
takes some time. encoding needs mfile. decoding needs gfile sfile pfile.
gen should be roughly a quarter megabyte of random data. gen without
enough random data may fail to generate a code. goppa will warn you in
that case.

goppa e mfile < plain > coded: encodes plain using mfile. plain is any
number of 82-byte blocks. actually the two high bits of the last byte of
each block are ignored: only 81 3/4 real bytes. you have to handle
padding. coded is same number of 128-byte blocks.

goppa d gfile sfile pfile < coded > plain: decodes coded using gfile,
sfile, pfile. will correct up to 37 bit errors in each 128-byte block.
goppa D gives some indication where bit errors are being corrected.

this program can trivially be used as a public-key system, where mfile
is the public key. all you have to do is add exactly 37 bit errors to
each 128-byte block. without gfile sfile pfile, the best known method of
decoding the result takes roughly 2^75 operations: millions of years
even if you put thousands of computers together. of course if gen is
known then gfile sfile pfile are known, so make sure gen is random. 
make sure it is cryptographically random because it is partly determined
by mfile which is public. also anyone who can guess the placement of bit
errors can decode the result. so make sure to place the bit errors very
randomly. also anyone who can guess your input can check to see whether
his guess is right. that's true of all public-key systems.

the above use of goppa coding is credited to mceliece. see a public-key
cryptosystem based on algebraic coding theory, deep space network
progress report 42-44 (1978), jpl, 114-116.

[stuff deleted. RMZ 1995]

prometheus

*/

#define sf(a,b) (sc[a^b]^sx[sc[a^sx[b]]]^sy[sc[a^sy[b]]])
#include <stdio.h>
#define O 1024
#define K 654
#define L 82
#define T 37
typedef unsigned short us;int sy[O],sx[O],sc[O],si[O],ss[O];us g[T+1];
us sq[T][T];int pe[1024];char st[K][L],su[K][L],sv[K][L];sm(a,b){a=
(a*(b&1))^(a*(b&2))^(a*(b&4))^(a*(b&8))^(a*(b&16))^(a*(b&32))^(a*(b&64))
^(a*(b&128))^(a*(b&256))^(a*(b&512));b=(a>>10)^((a>>7)&8184)^(a&1023);
return(b>>10)^((b>>7)&8184)^(b&1023);}
natsex(h,a)us*h;{int i,b,c;b=0;c=ss[a];for(i=T;i>=0;--i)b=h[i]^sf(b,c);
return b;}recsex(h,a)us*h;{int i,b,c;b=g[T];c=ss[a];for(i=T-1;i>=0;--i)
{h[i]=b;b=g[i]^sf(b,c);}return b;}snmsex(h,f,q)us*h,*f,*q;{us t[T+T+T];
int i,j;for(i=0;i<T+T+T;++i)t[i]=0;for(i=0;i<T;++i)for(j=0;j<T;++j)t[i+
j]^=sf(f[j],ss[q[i]]);for(j=T+T;j>=T;--j)if(t[j])for(i=1;i<=T;++i)t[j-i
]^=sf(g[T-i],ss[t[j]]);for(i=0;i<T;++i)h[i]=t[i];}sqshsex(h,f)us*h,*f;{
us t[T];int i,j;for(i=0;i<T;++i)t[i]=f[i];for(j=0;j<369;++j){snmsex(h,t
,t);for(i=0;i<T;++i)t[i]=h[i];}}sqrtsex(h,f)us*h,*f;{int i,j,d;for(i=0;
i<T;++i)h[i]=0;for(j=0;j<T;++j){d=ss[ss[f[j]]];for(i=0;i<T;++i)h[i]^=sf
(sq[j][i],d);}}funsex(h,f,m)us*h,*f;{static us v[T+T+1],q[T+T],w[T+T],x
[T+T];int i,j,k,d;for(i=0;i<T;++i)f[i]=!i;for(i=0;i<T;++i)q[i]=0;for(i=
0;i<=T;++i)v[i]=g[i];for(i=T-1;i>0;--i)if(h[i])break;d=ss[si[h[i]]];for
(j=T;j>=T-i;--j)v[j]^=sf(h[j-T+i],d);q[T-i]=sf(1,d);for(;;){for(i=T-1;i
>0;--i)if(v[i])break;if(i<m)break;d=ss[si[v[i]]];for(k=T-1-i;k>=0;--k){
w[k]=sf(h[i+k],d);if(w[k]){for(j=T-1;j>=k;--j){h[j]^=sf(v[j-k],ss[w[k]]
);f[j]^=sf(q[j-k],ss[w[k]]);}}}for(i=0;i<T;++i){x[i]=q[i];q[i]=f[i];f[i
]=x[i];x[i]=v[i];v[i]=h[i];h[i]=x[i];}}for(i=0;i<T;++i)h[i]=v[i];for(i=
0;i<T;++i)f[i]=q[i];}rn(m){int c,d;c=getchar();d=getchar();if((c==EOF)||
(d==EOF)){fprintf(stderr,"not enough gen material, dying\n");exit(1);}c=
((c&255)<<8)+(d&255);return c%m;}us x[O][T];char y[O][O/8];int z[O];us
w[O];main(argc,argv)char **argv;{int a,b,c,d,i,j;unsigned char l[O/8];
us f[T],h[T],q[T+1],s[T],tu[O],tv[O];char m[O/8];FILE *fi;
for(a=0;a<O;++a)ss[sm(a,a)]=a;for(a=0;a<O;++a)si[a]=0;for(a=0;a<O;++a)
tu[a]=1<<(a%10);for(a=1;a<O;++a)if(!si[a]){for(b=a;b<O;++b)if(!si[b]&&
sm(a,b)==1)break;c=d=1;do si[c=sm(a,c)]=d=sm(b,d);while(c-1);}for(a=0;
a<O;++a)tv[a]=1<<(a&7);for(a=0;a<O;++a)sc[a]=sm(a,sm(a,a));for(a=0;a<O
;++a)sy[sx[a]=sm(237,a)]=a;if(!argv[1]){fprintf(stderr,"g e or d please\n"
);exit(1);}if(argv[1][0]=='g'){for(i=0;i<T+1;++i)g[i]=1;for(;;){for(i=0
;i<T;++i)g[i]=rn(1024);for(a=0;a<O;++a)if(!recsex(h,a))break;if(a<O)
continue;for(i=0;i<T;++i)f[i]=0;f[1]=1;for(i=0;i<T*10;++i){snmsex(h,f,f
);for(j=0;j<T;++j)f[j]=h[j];}for(i=0;i<T;++i)if(f[i]!=(i==1))break;if(i
==T)break;}printf("1\n");for (a=0;a<O;++a){b=ss[si[recsex(x[a],a)]];for
(i=0;i<T;++i)x[a][i]=sf(x[a][i],b);for(i=0;i<O/8;++i)y[a][i]=0;y[a][a/8
]|=tv[a];}printf("2\n");for(a=0;a<O;++a)z[a]=-1;d=0;for(a=0;a<O;++a){i=
0;for(;;){while(!x[a][i/10]){++i;if(i==T*10)break;}if(i==T*10){w[d++]=a
;break;}while(!(x[a][i/10]&tu[i]))++i;if((c=z[i])==-1){z[i]=a;break;}for
(j=0;j<T;++j)x[a][j]^=x[c][j];for(j=0;j<O/8;++j)y[a][j]^=y[c][j];}if(d==
K)break;}printf("3\n");for(i=0;i<T;++i)sq[0][i]=!i;for(j=0;j<T;++j)h[j]=
(j==1);sqshsex(sq[1],h);for(i=2;i<T;++i)snmsex(sq[i],sq[i-1],sq[1]);
printf("4\n");for(i=0;i<O;++i)pe[i]=i;for(i=0;i<O;++i){j=rn(O-i)+i;d=pe[
j];pe[j]=pe[i];pe[i]=d;}printf("5\n");for(i=0;i<K;++i){for(j=0;j<O/8;++j
)m[j]=0;for(a=0;a<O;++a)if(y[w[i]][a/8]&tv[a])m[pe[a]/8]|=tv[pe[a]];for(
j=0;j<O/8;++j)y[w[i]][j]=m[j];}printf("6\n");for(;;){for(i=0;i<K;++i)for
(j=0;j<L;++j)sv[i][j]=st[i][j]=rn(256);for(i=0;i<K;++i)for(j=0;j<L;++j)
su[i][j]=0;for(i=0;i<K;++i)su[i][i/8]|=tv[i];for(i=0;i<K;++i){for(j=i;j
<K;++j)if(st[j][i/8]&tv[i]){if(i!=j)for(d=0;d<L;++d){c=su[j][d];su[j][d
]=su[i][d];su[i][d]=c;c=st[j][d];st[j][d]=st[i][d];st[i][d]=c;}for(d=0;
d<K;++d)if(d!=i)if(st[d][i/8]&tv[i])for(c=0;c<L;++c){su[d][c]^=su[i][c]
;st[d][c]^=st[i][c];}break;}if(j==K)break;}if(i==K)break;}printf("7\n");
argv+=2;if(!(fi=fopen(*argv?*argv++:"gfile","w"))){fprintf(stderr,
"gfile problem\n");exit(1);}for(i=0;i<=T;++i)fprintf(fi,"%hu\n",g[i]);for
(i=0;i<K;++i)fprintf(fi,"%hu\n",w[i]);for(i=0;i<T;++i)for(j=0;j<T;++j)
fprintf(fi,"%hu\n",sq[i][j]);fclose(fi);if(!(fi=fopen(*argv?*argv++:
"sfile","w"))){fprintf(stderr,"sfile problem\n");exit(1);}for(i=0;i<K;++
i)for(j=0;j<L;++j)fputc(su[i][j],fi);fclose(fi);if(!(fi=fopen(*argv?*argv
++:"pfile","w"))){fprintf(stderr,"pfile problem\n");exit(1);}for(i=0;i<O;
++i)fprintf(fi,"%u\n",pe[i]);fclose(fi);if(!(fi=fopen(*argv?*argv++:
"mfile","w"))){fprintf(stderr,"mfile problem\n");exit(1);}for(i=0;i<K;++
i){for(j=0;j<O/8;++j)m[j]=0;for(b=0;b<K;++b)if(sv[i][b/8]&tv[b])for(j=0;
j<O/8;++j)m[j]^=y[w[b]][j];for(j=0;j<O/8;++j)fputc(m[j],fi);}fclose(fi);
exit(0);}if(argv[1][0]=='e'){argv+=2;if(!(fi=fopen(*argv?*argv++:"mfile"
,"r"))){fprintf(stderr,"mfile problem\n");exit(1);}for(i=0;i<K;++i)for(j
=0;j<O/8;++j){y[i][j]=fgetc(fi);}fclose(fi);for(;;){for(i=0;i<L;++i){if(
(c=getchar())==EOF)break;l[i]=c;}if(!i)exit(0);if(i<L){fprintf(stderr,
"final block only %d bytes, ignored\n",i);exit(1);}for(j=0;j<O/8;++j)m[j
]=0;for(i=0;i<K;++i){d=!!((l[i/8]&tv[i]));if(d)for(j=0;j<O/8;++j)m[j]^=y
[i][j];}for(j=0;j<O/8;++j){putchar(m[j]);}}}if(argv[1][0]=='d'||argv[1][
0]=='D'){argc=(argv[1][0]=='D');argv+=2;if(!(fi=fopen(*argv?*argv++:
"gfile","r"))){fprintf(stderr,"gfile problem\n");exit(1);}for(i=0;i<=T;
++i)fscanf(fi,"%hu",&g[i]);for(i=0;i<K;++i)fscanf(fi,"%hu",&w[i]);for(i=
0;i<T;++i)for(j=0;j<T;++j)fscanf(fi,"%hu",&sq[i][j]);fclose(fi);if(!(fi=
fopen(*argv?*argv++:"sfile","r"))){fprintf(stderr,"sfile problem\n");
exit(1);} for(i=0;i<K;++i)for(j=0;j<L;++j)su[i][j]=fgetc(fi);fclose(fi);
if(!(fi=fopen(*argv?*argv++:"pfile","r"))){fprintf(stderr,"pfile problem\n"
);exit(1);}for(i=0;i<O;++i)fscanf(fi,"%u",&pe[i]);fclose(fi);for(;;){for
(j=0;j<O/8;++j){if((c=getchar())==EOF)break;l[j]=c;}if(!j)exit(0);if(j<O
/8){fprintf(stderr,"final block only %d bytes, ignored\n",j);exit(1);}for
(j=0;j<O/8;++j)m[j]=0;for(a=0;a<O;++a)if(l[pe[a]/8]&tv[pe[a]])m[a/8]|=tv
[a];for(i=0;i<T;++i)s[i]=0;for(a=0;a<O;++a)if(m[a/8]&tv[a]){b=ss[si[
recsex(h,a)]];for(i=0;i<T;++i)s[i]^=sf(h[i],b);}for(i=0;i<T;++i)if(s[i])
{funsex(s,h,1);d=ss[si[s[0]]];for(i=0;i<T;++i)h[i]=sf(h[i],d);h[1]^=1;for
(i=0;i<T;++i)if(h[i])break;if(i==T){m[0]^=tv[0];if(argc){fprintf(stderr,
"[%d]",0);fflush(stderr);}break;}sqrtsex(f,h);funsex(f,h,(T/2)+1);for(i=
(T+1)/2;i<T;++i)if(h[i])break;if(i<T){fprintf(stderr,
"too many errors in block\n");break;}q[T]=0;snmsex(q,f,f);snmsex(f,h,h);
for(i=1;i<=T;++i)q[i]^=f[i-1];for(a=0;a<O;++a)if(!natsex(q,a)){m[a/8]^=
tv[a];if(argc){fprintf(stderr,"[%d]",a);fflush(stderr);}}break;}for(i=0;
i<L;++i)l[i]=0;for(i=0;i<K;++i)if(m[w[i]/8]&tv[w[i]]){for(b=0;b<L;++b)l[
b]^=su[i][b];}for(i=0;i<L;++i)putchar(l[i]);}}
fprintf(stderr,"g e or d please\n");exit(1);}