## Sunday, June 29, 2014

### Why my encrypted value is different each time?

A few days ago, one guy at work asked me when using a crypto wrapper that I have written, why the encrypted value is different each time? For that crypto wrapper, I was simply using the C# RSACryptoServiceProvider [1], with a cert file as public key and a password protected pfx file containing the private key.

Well, it uses RSA [2] algorithm, and I think my colleague must have learned this at school, long time ago ;). The standard text-book RSA algorithm does not use padding so the encrypted value gets generated is same each time. That pretty much makes RSA not secure in real world because hackers can try different combinations to reproduce the same value instead of brute force solving what are the two prime numbers.

With that said, let’s review the basic of RSA in case you get asked some related questions in your interview. I am not a security expert in any means, just the most basic stuff.

1) Find two prime number, prefer large one, more than 100 bits, for example, P and Q, and let
N = P * Q
M = (P - 1) * (Q - 1)
2) Find a number E that is a relative prime of M, meaning the Greatest Common Divisor (gcd) of E and M is 1.
3) Find a number D, so that E * D mod M = 1.

With the above, now you have a public key E to encrypt your data, and you have your private key D to decrypt. N is also public.

For example, now you want to encrypt data X,
X^E mod N = Y

According to Fermat’s little theorem, you could decrypt Y with private D using
Y^D mod N = X

It is proved that without D, it will take extremely long time to figure out the two prime numbers given N. Until this point, if you are using the above method, the encrypted value should be the same every time using public key E. This is where padding coming into picture.

Take OAEP (Optimal Asymmetric encryption padding) Padding [3], it adds different numbers to the X before encrypting it so that the encrypted values are different each time. In decryption, it removes those values.

An interesting article written (in Chinese) by Dr. Jun Wu, while he was still at Google. If you can read Chinese, highly recommend you to read it.
http://www.kuqin.com/math/20071204/2796.html . His original blog was shut down, this was saved by some other people, you can also take a look at his book “数学之美” [4]

Reference:
[2] RSA:
[3] OAEP
[4] 数学之美

## Monday, June 23, 2014

### [电面基础]: Java基于Hashtable的问题讨论 哈希表 Continued

http://www.nurkiewicz.com/2014/04/hashmap-performance-improvements-in.html?m=1

Key take aways

1. When collision happens, instead of using a LinkedList, a Tree is used to cut of the search time from O(N) to O(lgN)
2. Reducing the collision costs will also prevent DOS in a way so that attackers can not send lots of hash-collision requests to slow down the servers.

## Saturday, June 14, 2014

### [电面基础]Java基于Map/Hashtable的问题讨论

“Have you used HashMap before?”  or “What is HashMap? why do we use it？”

• Hash相关的数据结构本质上都是key value pair;
• Hash中不能存在duplicate key;
• HashMap提供非常快速查找时间复杂度；
• 在HashMap具体实现中，Null可以作为key或者value存在；
• HashMap不是线程安全；

“What’s the difference between Hashtable and HashMap?”

• HashMap不提供线程安全，而Hashtable是线程安全；同样，在单线程环境下，HashMap的性能要比Hashtable好一些；（对于有线程安全需求的场景，可以使用Collections.synchronizedMap(HashMap) 来返回一个线程安全的HashMap)
• HashMap允许Null作为key或者value, Hashtable不允许；
• HashMap不保证内部元素的存储顺序；（遍历时无序）
• HashMap中的iterator是fast-fail iterator，Hashtable的不是；(具体讨论请参考下节Iterater/Emumeration）

"How HashMap works in Java?” or "How does get()/put() method of HashMap works in Java?"

HashMap自然是基于Hash实现的key-value pair。具体实现，一个HashMap在内部会维护一个key-value类型(Map.Entry<K, V>) 的数组。在get()/put()中，它使用定义好的hash()算出key object在内部数组中的索引，然后在get()/put()中做相应的存取。如果HashMap中的元素能够相对均匀的分布在数组中的时候，get()/put()是可以达到非常好的常数时间复杂度。

"What will happen if two different objects have same hashcode?” or "How will you retrieve Value object  if two keys will have same hashcode?”

“What happens On HashMap in Java if the size of the HashMap  exceeds a given threshold defined by load factor?” or “do you see any problem with resizing of HashMap  in Java?”