- 论坛徽章:
- 2
|
本帖最后由 damcool 于 2014-09-18 19:59 编辑
修改了大数除法的算法，一些其它优化，把效率提高了近3倍。900k文件2分多点。个人觉得很满意了！
更正大数求余，二分查找的一个bug.
encrypt.sh- #!/bin/bash
- #key="$(ifconfig|grep -o -E '([[:xdigit:]]{1,2}:){5}[[:xdigit:]]{1,2}'|head -1)"
- key="00:10:18:B1:FA:EF"
- # ^ ^ ^ ^ ^ ^
- # | | | | | |
- # 6 5 4 3 2 1
- ord="3:2:1:4"
- src_file="Suzhou.mp4"
- length=4
- echo "The file size of $src_file is $(stat -c %s $src_file) bytes." >&2
- now=$(date +"%s")
- for char in $(hexdump -ve "$length/1 \"%d \" \"\n\"" "$src_file"|awk -v ord="$ord" -v key="$key" -v l=$length -v ka="0x41C64E6D" -v kb="0x3039" -v kc="0x80000000" -f encrypt.awk); do printf "\\x$char"; done
- end=$(date +"%s")
- echo "It took $((end-now)) seconds to complete!" >&2
- function mod(p)
- {
- return (p%256)
- }
- function div(p)
- {
- return int(p/256)
- }
- function str_val(str, ret, chars, n, i, k, c)
- {
- if (str ~ /^0[0-7]*$/)
- {
- # octal
- n = length(str)
- ret = 0
- for (i = 1; i <= n; i++) {
- c = substr(str, i, 1)
- if ((k = index("01234567", c)) > 0)
- k-- # adjust for 1-basing in awk
- ret = ret * 8 + k
- }
- }
- else if (str ~ /^0[xX][[:xdigit:]]+/)
- {
- # hexadecimal
- str = substr(str, 3) # lop off leading 0x
- n = length(str)
- ret = 0
- for (i = 1; i <= n; i++) {
- c = substr(str, i, 1)
- c = tolower(c)
- if ((k = index("0123456789", c)) > 0)
- k-- # adjust for 1-basing in awk
- else if ((k = index("abcdef", c)) > 0)
- k += 9
- ret = ret * 16 + k
- }
- }
- else if (str ~ /^[-+]?([0-9]+([.][0-9]*([Ee][0-9]+)?)?|([.][0-9]+([Ee][-+]?[0-9]+)?))$/)
- {
- # decimal number, possibly floating point
- ret = str + 0
- }
- else ret = "NOT-A-NUMBER"
- return ret
- }
- function hex_ary(p, ary)
- {
- p=str_val(p);
- ary="";
- while(p>0)
- {
- ary=sprintf("%s:%d",ary,mod(p));
- p=div(p)
- }
- ary=substr(ary,2);
- return ary
- }
- function b_mul(a,b,c, i,j,m,n)
- {
- m=length(a);n=length(b);
- for(i=1;i<=m;i++) for(j=1;j<=n;j++)
- {
- c[i+j-1]+=a[i]*b[j];
- c[i+j]+=div(c[i+j-1])
- c[i+j-1]=mod(c[i+j-1]);
- }
- for(i=length(c);i>0;i--) if (i>1 && c[i]<1) delete c[i];
- }
- function ary_com(a,b, i,m,n)
- {
- m=length(a);n=length(b);
- for(i=m;i>0;i--)
- {
- if (i>n && a[i]>0) return 1;
- if (i<=n && a[i]>b[i]) return 1;
- if (i<=n && a[i]<b[i]) return -1;
- }
- return 0;
- }
- function b_mod(a,b,c, i,j,p,la,lb,lc,ll,rr,r)
- {
- la=length(a);lb=length(b);
- if ((la<2 && a[1]<1)||la<lb||(la==lb && a[la]<b[la]))
- {
- split(sprintf("%0"la"d",0),c,"");
- for(i=1;i<la;i++)c[i]=a[i];
- return
- }
- split(sprintf("%0"(lb+1)"d",0),c,"");
- for(i=1;i<=lb;i++) c[i]=a[la-lb+i];c[lb+1]=0;
-
- for (i=la;i>=lb;i--)
- {
- p=0;
- if (c[lb+1]*256+c[lb]>=b[lb])
- {
- ll=0;rr=255;
- while(ll<=rr)
- {
- pt=int((ll+rr)/2);
- split(sprintf("%0"(lb+1)"d",0),r,"");
- for (j=1;j<=lb;j++)
- {
- r[j]+=b[j]*pt;
- r[j+1]+=div(r[j]);
- r[j]=mod(r[j]);
- }
- j=ary_com(c,r);
- if (j==0)
- {
- p=pt;
- break;
- }
- if (j<0) rr=pt-1
- else ll=pt+1;
- }
- p=(j==0)?p:ll-1;
- }
- if (p>0)
- {
- for(j=1;j<=lb;j++)
- {
- c[j]-=b[j]*p;
- c[j+1]+=div(c[j]-255);
- c[j]=mod(mod(c[j])+256);
- }
- }
- if (i>lb)
- {
- for(j=lb;j>0;j--) c[j+1]=c[j];
- c[1]=a[i-lb];
- }
- }
- }
-
- BEGIN{
- split(key,ks,":");
- split(ord,o,":");
- for(i=1;i<=l;i++) k[i]=str_val(sprintf("%s%s","0x",ks[length(ks)+1-o[i]]));
- split(hex_ary(ka),a,":");
- split(hex_ary(kb),b,":");
- split(hex_ary(kc),c,":");
- h=l;
- la=length(a);
- lb=length(b);
- lc=length(c);
- h=(h<la)?la:h;
- h=(h<lb)?lb:h;
- h=(h<lc)?lc:h;
- }
- {
- for(i=1;i<=NF;i++) printf "%02X ",xor(k[i],$i)
- if (NF<l) exit;
-
- #caculate k*a+b
- now=systime();
- delete t;
- delete d;
- for(i=1;i<=2*h;i++)t[i]=(i>lb)?0:b[i];
- for(i=1;i<=l;i++) d[i]=k[o[i]];
- b_mul(d,a,t)
-
-
- end=systime()
- kab+=end-now;
- #caculate "%c"
- now=systime();
- b_mod(t,c,q);
- end=systime()
- kabc+=end-now
- #get new key
- for(i=1;i<=l;i++) k[o[i]]=q[i];
- }
- END{
- printf "[DEBUG:Caculation of (k*a+b) took %d seconds]\n",kab|"cat >&2";
- printf "[DEBUG:Caculation of (k*a+b)%%c took %d seconds]\n",kabc|"cat >&2";
- }
- > date;sh encrypt.debug.sh|hexdump -C;date
- 2014年09月18日 11:44:52
- The file size of test is 13 bytes.
- [DEBUG:Caculation of (k*a+b) took 0 seconds]
- [DEBUG:Caculation of (k*a+b)%c took 0 seconds]
- It took 0 seconds to complete!
- 00000000 f9 9f 83 74 79 f9 ab 6d 7f a4 e1 4e df |...ty..m...N.|
- 0000000d
- 2014年09月18日 11:44:52
- >
- [@:~]> date;sh encrypt.debug.sh>test.awk.ret;date
- 2014年09月18日 19:50:31
- The file size of Suzhou.mp4 is 935748 bytes.
- [DEBUG:Caculation of (k*a+b) took 9 seconds]
- [DEBUG:Caculation of (k*a+b)%c took 101 seconds]
- It took 129 seconds to complete!
- 2014年09月18日 19:52:40
|
|
免费注册
楼主: bikkuri
发表于 2014-09-17 15:38
