火车运煤算法

 算法  火车运煤算法已关闭评论
2月 192016
 

转自:http://flychao88.iteye.com/blog/2187854

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大――每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

 

这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。

 

思考答题是

  1. 装1000吨煤,走250公里,扔下500吨煤,回矿山。
  2. 装1000吨煤,走到250公里处,拿起250吨煤继续向前到500公里处,扔下500吨煤,回矿山。此时火车上还有250吨,再加上在250公里处还有250吨煤,所以,火车是可以回矿山的。
  3. 装上最后1000吨煤,走到500公里处,装上那里的500吨煤,然后一直走到目的。
 Posted by at 上午 10:57

公钥基础设施中的密钥格式及密钥结构

 算法, 网络安全  公钥基础设施中的密钥格式及密钥结构已关闭评论
5月 142014
 

缘起

同一个密钥可以保存成多种格式,不同的语言对密钥的格式还有偏好,不都是一段字符嘛,干嘛整这么多名词?

 

参考资料:

https://polarssl.org/kb/cryptography/asn1-key-structures-in-der-and-pem

http://www.cryptopp.com/wiki/Keys_and_Formats#RSA_PublicKey

 

 Posted by at 下午 7:01

今天最郁闷的事(RC4)

 算法, 编码, 网络安全  今天最郁闷的事(RC4)已关闭评论
4月 242014
 

缘起

由于需要,引入了rc4加密算法,网上搜到了一些PHP实现,Java实现,当然,对于PHP来讲,还有openssl的实现。

网址: http://zhiwei.li/text/2011/08/7777777777777777777/

上还证明了PHP的实现和openssl的实现是相同的,由于该网址有测试例子,自己执行一边,果然如该网址所言。

由于存在java实现的需要 ,于是就测试一下,java实现和PHP实现是否相同,由于PHP的实现和openssl的实现相同,于是只比较了openssl 和java的解密结果,果然不让人省心,结果是:不同!

开始折腾

好在rc4的算法比较简单,怀疑可能是网上找到的java版本实现有问题,参考PHP的实现,自己实现了一遍java版本,结果让人纠结,自己实现的和网上找到的结果完全一样,问题在哪里?

当我再次比较openssl和php的加密结果时:发现加密结果100%不同。事情进展到这个地步,更显扑朔迷离,怀疑自己原来测试的有问题,再次测试N边,依然没有问题,其不叫人发疯。

最后,再拿出 http://zhiwei.li/text/2011/08/7777777777777777777/ 来研究;发现里面的key是md5一个密钥字符串后再pack得到的,这个也有关系?试试吧,果然有关系。至此,想起来自己两次测试使用的key是不同的,成功的那次测试,key刚好也是16字节的,而失败的那次测试的key是“testkey”,才想起来,openssl在做加密时,如果key不够长(16字节),则会在后面补 “\0″(是零,不是圈儿),但是自己实现的RC4算法,是没有在key后面补 “\0” 的。

真相大白。

郁闷啊

附测试脚本:

 

 

 

 Posted by at 下午 6:54

JAVA使用openssl生成的公私钥做加密解密

 Java, 算法, 网络安全, 默认分类  JAVA使用openssl生成的公私钥做加密解密已关闭评论
1月 262013
 

使用openssl生成密钥对:

 

java代码:

1. 注意: java 语言本身没有实现base64编码,而openssl生成的密钥对一般做base64编码,便于维护,所以这里引用了 org.apache.commons.codec.binary.Base64;

 

稍后提供一个PHP加密Java解密的实现

 

参考资料:

http://stackoverflow.com/questions/11787571/how-to-read-pem-file-to-get-private-and-public-key

http://stackoverflow.com/questions/8647165/how-to-sign-a-generic-text-with-rsa-key-and-encode-with-base64-in-java

http://www.javamex.com/tutorials/cryptography/rsa_encryption.shtml

http://snowolf.iteye.com/blog/381767

密钥结构及格式: https://polarssl.org/kb/cryptography/asn1-key-structures-in-der-and-pem

 

 

 

 Posted by at 下午 8:22

crc32算法原理

 算法  crc32算法原理已关闭评论
9月 102011
 

Cyclic Redundancy Check循环冗余检验,是基于数据计算一组效验码,用于核对数据传输过程中是否被更改或传输错误。 算法原理 假 设数据传输过程中需要发送15位的二进制信息g=101001110100001,这串二进制码可表示为代数多项式g(x) = x^14 + x^12  + x^9 + x^8 + x^7 + x^5 +  1,其中g中第k位的值,对应g(x)中x^k的系数。将g(x)乘以x^m,既将g后加m个0,然后除以m阶多项式h(x),得到的(m-1)阶余项 r(x)对应的二进制码r就是CRC编码。
h(x)可以自由选择或者使用国际通行标准,一般按照h(x)的阶数m,将CRC算法称为CRC-m,比如CRC-32、CRC-64等。国际通行标准可以参看http://en.wikipedia.org/wiki/Cyclic_redundancy_check
g(x)和h(x)的除运算,可以通过g和h做xor(异或)运算。比如将11001与10101做xor运算:      
明白了xor运算法则后,举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1,既h是9位的二进制串111010101。

      
经过迭代运算后,最终得到的r是10001100,这就是CRC效验码。
通过示例,可以发现一些规律,依据这些规律调整算法:

1. 每次迭代,根据gk的首位决定b,b是与gk进行运算的二进制码。若gk的首位是1,则b=h;若gk的首位是0,则b=0,或者跳过此次迭代,上面的例子中就是碰到0后直接跳到后面的非零位。
               

2. 每次迭代,gk的首位将会被移出,所以只需考虑第2位后计算即可。这样就可以舍弃h的首位,将b取h的后m位。比如CRC-8的h是111010101,b只需是11010101。

      

3. 每次迭代,受到影响的是gk的前m位,所以构建一个m位的寄存器S,此寄存器储存gk的前m位。每次迭代计算前先将S的首位抛弃,将寄存器左移一位,同时将g的后一位加入寄存器。若使用此种方法,计算步骤如下:

      
※蓝色表示寄存器S的首位,是需要移出的,b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S’是经过位移后的S。

查表法 同样是上面的那个例子,将数据按每4位组成1个block,这样g就被分成6个block。
      
下面的表展示了4次迭代计算步骤,灰色背景的位是保存在寄存器中的。

      

经4次迭代,B1被移出寄存器。被移出的部分,不我们关心的,我们关心的是这4次迭代对B2和B3产生了什么影响。注意表中红色的部分,先作如下定义:

   B23 = 00111010
   b1 = 00000000
   b2 = 01010100
   b3 = 10101010
   b4 = 11010101
   b’ = b1 xor b2 xor b3 xor b4

4次迭代对B2和B3来说,实际上就是让它们与b1,b2,b3,b4做了xor计算,既:
   B23 xor b1 xor b2 xor b3 xor b4
可以证明xor运算满足交换律和结合律,于是:
   B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b’
b1是由B1的第1位决定的,b2是由B1迭代1次后的第2位决定(既是由B1的第1和第2位决定),同理,b3和b4都是由B1决定。通过B1就可以计 算出b’。另外,B1由4位组成,其一共2^4有种可能值。于是我们就可以想到一种更快捷的算法,事先将b’所有可能的值,16个值可以看成一个表;这样 就可以不必进行那4次迭代,而是用B1查表得到b’值,将B1移出,B3移入,与b’计算,然后是下一次迭代。

      
可看到每次迭代,寄存器中的数据以4位为单位移入和移出,关键是通过寄存器前4位查表获得
,这样的算法可以大大提高运算速度。
上面的方法是半字节查表法,另外还有单字节和双字节查表法,原理都是一样的——事先计算出2^8或2^16个b’的可能值,迭代中使用寄存器前8位或16位查表获得b’。

反向算法之前讨论的算法可以称为正向CRC算法,意思是将g左边的位看作是高位,右边的位看作低位。G的右边加m个0,然后迭代计算是从高位开始,逐步将低位加入到寄存器中。在实际的数据传送过程中,是一边接收数据,一边计算CRC码,正向算法将新接收的数据看作低位。
逆向算法顾名思义就是将左边的数据看作低位,右边的数据看作高位。这样的话需要在g的左边加m个0,h也要逆向,例如 正向CRC-16算法h=0x4c11db8,逆向CRC-16算法h=0xedb88320。b的选择0还是h,由寄存器中右边第1位决定,而不是左边 第1位。寄存器仍旧是向左位移,就是说迭代变成从低位到高位。

0
0

0 [end

 Posted by at 上午 12:47