理解橢圓曲線密碼學(Elliptic Curve Cryptography)

橢圓曲線方程式:
   G(x,y) :: y² = x³  + a*x + b   其中 4a³ + 27b² != 0
P Q R 是在橢圓曲線的3個點, 並且都同在一個直線上:
         P + Q + R = O (橢圓曲線零點)
上式並不是算術運算的加法, 只是一個術語.
         因此 P + Q = - R
負數代表的是鏡像(mirror), 因為橢圓曲線對於 Y 軸而言是一個對稱曲線, 因此可以想像成 R 與 -R 是分別在 Y 正負軸上面等距離的點
已知 P=G(x1,y1), Q=G(x2,y2) 求解 R=G(x3,y3), 帶入上述橢圓曲線G(x,y)及直線方程式L(x,y), 經由係數比較就可得出 x₃ = s² - x₂ - x₁的關係式
       曲線 G(x,y) :: y² = x³  + a*x + b               
       直線 L(x, y) :: y = s*x + c
條件(一) 當 P != Q 時, 使用一般直線斜率 s 的加法運算求出 R:
      s = ( y2 - y1 ) / (x2 - x1 )
      x3 = s² - x2 - x1
      y3 = s*(x2-x3) -  y2
條件(二) 當 P == Q 時,  x1=x2, 且 y1=y2, 運算斜率 s 時, 導致除零的錯誤, 要改用雙倍切線斜率運算:
      s = ( 3 *x1² +a )/ ( 2y1)
      x3 = s² - 2x1
      y3 = s*(x1  -x3) - y1
條件(三) n(n>1)倍G運算, 使用雙倍運算及累加運算(DAA),演算法用2進位法:
      (1) 找出 n 當中最高位元是 1 時, 並開始初始化 R
               R = G ; // 初始化 R 等於 G(x,y)
               k = 要處理的位元數                  
      (2) while( k-- > 0 ) { // 累進運算
               R= optDouble(R);// 先將點作兩倍運算, 用上述條件(二)的雙倍運算
               if(  n.testBit(k) ) R=optINC(R, G); //當n測試到位元 1 時執行上述條件(一)的加法運算

           } //  重複步驟2直到 k = 0 為止
ECC 的對稱加密通信演算法:
當有兩端要通訊時, 兩邊各選擇一個整數(通常是大整數)當成私鑰, 將它乘上 G就形成 public key例如 pubA = a * G, pubB =b * G, 兩邊交換後, A 將收到的 pubB 乘上自己的私鑰,B收到pubA也乘上自己的私鑰, 結果 a*pubB = a*b*G = b *a * G = b * pubA 就是共用金鑰( a*b=b*a)所對應 ECC 上的一點, 把該點的資訊當作 AES 加解密之密碼, 傳輸的資料經 AES 加密過, 對外人來說是一串亂碼, 就算中間 pubA 或 pubB 被擷取, 也很難算出 a, b , a*b 來. 因為 a, b 對局外人來講是未知(大整)數, 只有通信方兩端知道自己的私鑰(a, b)及共同金鑰(ab)所對應的點ab *G(x,y), 實際上兩邊通信方也很難推算出共用金鑰 ab, 因此 ECC 可以讓通信保密

實際上觀念很簡單, 使用小整數來說:
1. Alice 與 Bob 共同約定使用相同ECC編碼,橢圓曲線(EC)上的點假設是 G(x,y)當作初始點.
2. Alice 使用 3 當作密鑰, Alice 將 3*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xp,yp), 實際上G(xp,yp)就是 Alice 的公開鑰匙, 將它傳給 Bob.
3.  Bob 使用 5 當作密鑰, 並將 5*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xq,yq), 實際上G(xq,yq)就是 Bob 的公開鑰匙, 將它傳給 Alice.
4. Alice 和 Bob 分別用自己的私鑰乘上所收到點的資訊並重新映設到新的橢圓曲線上一點,例如 Alice收到G(xq,yq), 而 Bob收到G(xp,yp), 實際上乘上自己的鑰匙後得到:
            Alice: 3*G(xq,yq) = 3*5*G(x,y) = 15*G(x,y)
            Bob:   5*G(xp,yp) = 5*3*G(x,y) = 15*G(x,y)
因此 3*5 稱為可以稱之共同金鑰, 而15*G(x,y) 是 ECC 上的一個點, 雖然兩邊很難算出 15 這個數字, 但可以利用該點共同座標當作訊息替後續要傳送的資料加以編碼(例如用 SHA-256 轉成亂數當成 AES-256 的密碼將訊息編碼). 重頭到尾, 外人無法得知 3, 5, 15 這個數字, 外人只能察覺到兩人在交換 ECC 上點的資訊(公開鑰匙), 如果要反推 3,5,15, 便需要從頭 G(x,y)一一去嘗試, 一旦試到 15 才能找到答案.但密碼學裡很重要的觀念是'數'的量很龐大,當我們使用超級大整數時例如 256 bit來將私鑰編碼時就有 2的256次方個組合, 這根本是一個無法想像的數字.而 ECC 點的運算,必需從頭到尾一一加以運算, 就算知道起點和終點,仍然很難分解出該私鑰點所對應的之相對位置. 更遑論是大整數的運算了. 當駭客無法破解密碼時,唯一可以用的方法是暴力窮舉法一一測試, 但由於是大整數的關係, 要一直不斷嘗試, 真的非常困難. 這就是 ECC 相當安全的重要原因.

ECC 使用的 ElGamal 非對稱加解密通信演算法:
1. 兩人約定用 ECC 的點 G(x, y) 當作通訊協定
2. Alice 挑選一個私鑰  a, 算出 ECC 上的一點座標 PA 傳給 Bob, PA 就是 Alice 公鑰:
     座標 PA:: a*G(x, y) = G(x_a, y_a)
3. Bob 收到後, 也隨機挑選一個密鑰 b, 算出 ECC 上的一點當自己的公鑰 PB, 同時把要加密的文件訊息 m 用 Alice 的公鑰編碼成 R, 為了能適用 ECC 的加法運算, m 必須映射到橢圓曲線上, 有一種方式是將 m 當成 x 帶入曲線公式解出 y 得出座標(x_m,y_m), 再計算編碼過的座標 R = m + b*PA,  連同 PB 一起回傳給 Alice, 讓她用私鑰將 m 解讀出來, 通信過程就算公開了 G(x_a,y_a) 與 G(x_b,y_b) 的座標點, 也很難猜到 G(x_ab,y_ab) 的座標點 , 因此外人解出 m 的機會很渺茫, 只有兩邊通信方知道共用金鑰 ab 座標點是G(x_ab, y_ab), 直接卸下(減掉)該因子就能快速還原文件訊息 m:
     座標 PB:: b*G(x, y) = G(x_b, y_b)
     座標 R:: m + b*PA(x, y) = m + G(x_ab, y_ab) = m + G(x_ba, y_ba)
4. Alice 收到 PB, R後, 就用自己的私鑰 a 去計算  R - a*PB 得出 m
     座標 (R  -  a*PB) :: [m + G(x_ab,y_ab)]  - G(x_ab,y_ab) = m + O = m
5.  ECC 的鏡射點相加是為零點 O:
     - G(x_ab, y_ab)  + G(x_ab, y_ab)  = O
6. 鏡射點, 實際上只要反轉 y 座標為負值:
     - G(x_ab, y_ab) = G(x_ab, - y_ab)
   m = R - G(x_ab, y_ab) = R + G(x_ab, - y_ab) 利用ECC 的加法運算就可算出座標值 (x_m, y_m), 其中的 x_m 就是解出來的訊息

Android 讀取加速度, 亮度, 接近等三種感應器

// 主程式: MainActivity.java

package com.example.mint.accelerometer;

import android.hardware.Sensor;
import android.hardware.SensorEvent;
import android.hardware.SensorEventListener;
import android.hardware.SensorManager;
import android.os.Bundle;
import android.support.v7.app.AppCompatActivity;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity  implements SensorEventListener {
    SensorManager sensorMan;
    TextView textview;
    String accMeter, lightMeter, proximityMeter;
    public void onAccuracyChanged(Sensor arg0, int arg1) {
    }
    public void onSensorChanged(SensorEvent event) {
        switch( event.sensor.getType() ) {
            case Sensor.TYPE_ACCELEROMETER:
                accMeter = "\n加速感應器: x=" + event.values[0] + "    y=" + event.values[1] + "    z=" + event.values[2];
                break;
            case Sensor.TYPE_PROXIMITY:
                proximityMeter = "\n接近感應器:" + event.values[0];
                break;
            case Sensor.TYPE_LIGHT:
                lightMeter = "\n亮度感應器:" + event.values[0];
                break;
        }
        textview.setText(accMeter+proximityMeter+lightMeter);
    }
    @Override    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        textview = (TextView)findViewById(R.id.meterInfo);
        sensorMan = (SensorManager) getSystemService(SENSOR_SERVICE);
    }
    protected void onResume() {
        super.onResume();
        sensorMan.registerListener(this, sensorMan.getDefaultSensor(Sensor.TYPE_ACCELEROMETER), SensorManager.SENSOR_DELAY_NORMAL);
        sensorMan.registerListener(this, sensorMan.getDefaultSensor(Sensor.TYPE_PROXIMITY), SensorManager.SENSOR_DELAY_NORMAL);
        sensorMan.registerListener(this, sensorMan.getDefaultSensor(Sensor.TYPE_LIGHT), SensorManager.SENSOR_DELAY_NORMAL);
    }

    @Override    protected void onPause() {
        super.onPause();
        sensorMan.unregisterListener(this);
    }

}

// activity_main.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context="com.example.mint.accelerometer.MainActivity">
    <TextView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Hello World!"
        android:id="@+id/meterInfo" />
</RelativeLayout>

使用 gulp.js 讓流程自動化

gulp 中文語意是:吞嚥, 我覺得翻譯成 '嗑' 比較貼切. 它就是將東西吞下去. 當我們寫了許多Javascript 要將它整合成一個檔案並將它醜化,需要通過工具程式及一些流程來完成. 當然用Makefile 就可做到, 但寫個 Makefile 很麻煩,要考慮檔案的相關性,用 gulp.js 很直覺就能直接使用,且他是用 Javascript 語法, 對於寫 Javascript 來說相當便利.但 gulp.js 可不只這樣, 他還可以讓各個流程同時進行.先簡單以上述例子來練習. 先用 sudo npm -g 來安裝 gulp 及 requirejs , linux mint 會將它放在 /usr/lib/node_modules 目錄裏面:
                       sudo npm install gulp requirejs -g
再切換到專案目錄,安裝所需要的工具模組(例如串接檔案成單一個, 去醜化等):
                       cd /home/mint/myproject
                       npm install gulp-concat gulp-uglify
接著寫一個 gulpfile.js 讓 gulp 根據文件內容去執行.下面例子是將 1.js, 2.js, 3.js 結合成單一檔案 my.js, gulp.task 用來自訂一個流程, 第一個參數是自定的名稱, 第2個參數是匿名函數,實現
流程化, 在流程化裏面可以直接套用 gulp 的函數諸如 .src .pipe .dest 等等. 通過管線(.pipe)就可以將輸出/入檔案相互串接,達到想要完成的目的(流程).

         // gulpfile.js
         var gulp = require('gulp');
         var concat = require('gulp-concat');
         var uglify = require('gulp-uglify');
         gulp.task('combine', function() {
                  // .src( string_array ) -> .pipe(function( )  ) -> .pipe( function( ) ) -> .pipe( function( ) )
         gulp.src(['1.js', '2.js', '3.js']).pipe(concat('my.js')).pipe(uglify()).pipe(gulp.dest('build/'));
         });

最後要執行該流程時,將流程名稱提供給 gulp, 鍵入以下命令:

         gulp combine

在 build/ 目錄內就會生成一個醜化過後的檔案  my.js
對於其他檔案例如 index.htm 想要複製到 build 目錄裏面時, 也可以自定一個流程將檔案複製過去:
         gulp.task('copy', function() {
                  gulp.src('index.htm').pipe(gulp.dest('build/'));
         });
將所有的流程集合到一個字串陣列,並命名一個 gulp 內定名稱 'default', 就可以讓上述兩個流程同時進行:
          gulp.task('default', ['combine', 'copy']);
完整的內容如下:
         // gulpfile.js
         var gulp = require('gulp');
         var concat = require('gulp-concat');
         var uglify = require('gulp-uglify');
         gulp.task('default', ['combine', 'copy']);
         gulp.task( 'combine', function() {
                gulp.src(['1.js', '2.js', '3.js']).pipe(concat('my.js')).pipe(uglify()).pipe(gulp.dest('build/'));
         });

         gulp.task('copy', function() {
                  gulp.src('index.htm').pipe(gulp.dest('build/'));
         });

要執行上述並行流程並不需要再提供流程名稱, gulp 會先找到 qulpfile.js, 再到檔案裏面找尋 default 這個流程名稱,解析它並自動執行,因此只要鍵入以下命令就可:

          gulp

另外在 linux 下面透過 cat 其實就可以將檔案合併, 透夠管線, 一條指令就可以達到上述同樣功能了:
          cat 1.js 2.js 3.js | ugilfyjs > my.js