Understanding Elliptic Curve Cryptography（橢圓曲線加密學）

要理解 ECC, 首先要了解 Elliptic Curve 的特性和定義。

以下內容會以最簡單的方式表達。

1. Elliptic Curve 的定義：

• y^2 = x^3 + ax + b
• 當中 4a^3 + 27b^2 != 0 （有 cusp 或者 self-intersection 交點的曲線都不算 Elliptic Curve）

符合 EC 的例子（a = -7 , b = 10）：

---

2. Elliptic Curve 的特性：

• 用圖片表示的話，你會發現所有 EC 都會有 P+Q+R=0 的特性
• （注意：這裏用的 P/Q/R 並非普通座標計算，而是有特定的公式）

用圖片表達，你會發現以下的現象：

為了方便日後討論，我們重新定義 EC 的加法「＋」和乘法「・」的意思：

加法 (Algebraic Addition)： 

• 假設 P != Q，斜率 m = ( y_p - y_q ) / ( x_p - x_q )
• 如果 P = Q，斜率 m = 3x_p^2 + a / 2y_p （如果用上一條式，除 0 計不到啊）
• R = ( x_r , y_r  ) , x_r = m^2 - x_p - x_q , y_r = y+p + m(x_r - x_p)

乘法 (Scalar Multiplication)：

• 這個簡單得多，n・P 不就是 P + P + ... + P 共 n 次嗎？
• 所以計法就是不斷用上面的加法，一直加到 n 次
• （但如果真的加 n 次，計算時間就會太繁複，所以有人想到用 double and add 的方法加速，在此不述）

---

3. 加了餘數 (modulo) 的 EC 公式

加了餘數的公式將會變成：

• y^2 = (x^3 + ax + b) mod p
• 當中 (4a^3 + 27b^2) != 0 mod p 
• 假設 P != Q，斜率 m = ( y_p - y_q )*( x_p - x_q )^-1 mod p
• 如果 P = Q，斜率 m = (3x_p^2 + a)*(2y_p)^-1 mod p 
• R = ( x_r , y_r  ) , x_r = (m^2 - x_p - x_q) mod p , y_r = [ y+p + m(x_r - x_p) ] mod p

可見即使加了 mod，P+Q+R = 0 的特性仍然生效，而且公式也很像樣（數學證明在此不述）。

以下圖表則是 mod 版本的 EC：

---

4. 找出重複規律

Mod 版的 EC 在不斷進行 P 點相加後，會出現重複規律。

例如 y^2 = (x^3 -x + 3) mod 37，如果從 P=(2,3) 開始，每加 7 次就會出現 R = (0,0) 

我們要找出其最小規律 (subgroup order n) ，任由選一個規律倍數 (order N)，

並且只用這個規律中的餘因子 (cofactor h = N/n) 來進行加密。

例子：y^2 = (x^3 -x + 3) mod 37, n = 7, N = 7, 14, 21, 28, 42, 49 ...

最後，G = h・P 將會用作加密用途。

h 會成為私密鑰匙。對方如果想找出 h，唯一方法就只有不斷加 P。
同時，因為每次加 P 都要用 double and add，相比傳統 RSA，破解時間會較長。

---

5. 用作非對稱加密 (Asymmetric Encryption)

公鑰 (Public Key): a, b, p, G, P 

私鑰 (Private Key): h

加密 M ：C = {kP, M + kG} （k 只有發送者知道）

解密 C：M + kG - hkP = M + khP - hkP = M

---

6. 用作交換共同金鑰 (EC Diffie-Hellman Key Exchange)

假設 Alice 和 Bob 均使用同一點 G:

Alice 公鑰 (Public Key): Ha = da・G 

Alice 私鑰 (Private Key): da

Bob 公鑰 (Public Key): Hb = db・G

Bob 私鑰 (Private Key): db

Alice 計算出 S = da・(Hb) = da・db・G

Bob 計算出 S = db・(Ha) = db・da・G

所以，他們就能有同一條金鑰 S 用作對稱加密。

---

7 . 用作簽署 (ECDSA)

由於只是 DSA 協議的變種，在此不再詳述。

---

參考資料：

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

http://course.ece.cmu.edu/~ece733/lectures/21-intro-ecc.pdf

http://amitmason.blogspot.com/2016/08/elliptic-curve-cryptography_37.html
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

CX4024 Lecture 4 - 2018, Anwitaman Datta, Nanyang Technological University

前向保密 (Forward Secrecy) 與後向保密 (Backward Secrecy)

Having said that there are many online resources discussing these two terminologies, it's actually quite easily mixed up - even for me. I was able to understand this topic a few weeks ago but turns out I forgot and mixed them up again.

According to [1], the story of Forward Secrecy and Backward Secrecy should be:

In short, because Gunther believes the session key exposure will happen in the future, so he used the word "forward" to indicate the current session key is not compromised by the "future" key leaks.

To simplify:

• Forward Secrecy: If the current session key is exposed, previous session messages are still safe.（即使現時的 session key 曝光，舊 sessions 的資料仍然安全）
• Backward Secrecy: If the current session key is exposed, the next session messages are still safe.（即使現時的 session key 曝光，下一個 session 的資料仍然安全）

Another graphical explanation from [2]:

In order to reduce confusion, the author tends to use new definitions "past/future secrecy":

• Forward Secrecy  = Past Secrecy, the word past means to protect past data.
• Backward Secrecy = Future Secrecy, the word future means to protect future data.

----

The next question would be, what algorithm can offer forward secrecy?

Hash Rachet is a very simple algorithm offering forward secrecy only:

Using the hashed current session key to encrypt the next session, even if the eavesdropper can decrypt the next session message and the session key, he cannot easily find back the last session keys because unhashing the session key results in many possible key (FYI: hash function is many-to-one).

---

Obviously, having forward secrecy is not enough, so Diffie-Hellman Ephemeral (DHE) is the way to offer both forward and backward secrecy.

Rules of DHE:

• Create a new shared common key in every session (ephemeral = short period of time)
• Use Diffie-Hellman to share the common key

Therefore:

• Every session is encrypted with a new common key unrelated to the previous session.
• Even if the current session key is exposed, since the next key is irrelevant to current key, it is hard to find unless the eavesdropper cracks the Diffie-Hellman.

---

Some protocols such as Signal has a combined use of both two methodologies above.
Largely because:

• DHE involves computational complexity, so the key update will not be so frequent. In this case, in order to protect the previous communication, Hash Rachet should still be used.
• To provide extra security - even if DHE is broken, previous messages should still be protected by Hash Rachet.

---

Citations:
[1]: Wang, M. & Yan, Z. Mobile Netw Appl (2017) 22: 195. https://doi.org/10.1007/s11036-016-0741-5
[2]: https://materials.dagstuhl.de/files/16/16353/16353.DominikSchuermann.Slides.pdf

Git 實用操作筆記

 

Forcibly cleaning everything including the directory, to make it clean again:
強行清除所有未 commit 的內容：

git clean -fd

git clean -nd (n is for preview, you can also use i for interactive)

Update everything from server
由 Server 取得更新：

git pull (--all)

Force manually update things from server
以 server 內容取代本機的內容：

git fetch

git reset --hard HEAD

----
放一個檔案去 Staged Area

# stage a file to staged area (a.k.a. add)

git add <filename>

git add -p <filename> #support --patch

反向操作

# unstage a file from staged area

git reset <filename>

git reset -p <filename> #support --patch

----

Reverting all changes to the latest commit, a.k.a. HEAD (discard changes) (for specific file, git checkout file is fine)
強行返回上一個 commit

git reset --hard HEAD

Move HEAD to previous commit
將 HEAD 指回上一個 commit

git reset --hard HEAD~1     #delete everything not committed.

git reset --soft HEAD~1     #keep unstaged things unchanged, combine HEAD~1 things and staged things to staged area

git reset --mixed HEAD~1    #(default) put all (HEAD~1 things, staged things and unstaged things) to unstaged area

Graphical Explanation: https://dotblogs.com.tw/wasichris/2016/04/29/225157

Move HEAD to specific commit 
將 HEAD 移到某一個 commit

git reset --hard 0d1d7fc32

#regret about the reset changes

git reflog                    # to list all history

git reset --hard HEAD@{5}     # to reset back to original HEAD (use HEAD 5 as example)

# reverting single file to latest commit

git checkout -- filename

----

Save temporary changes without commit, then display clean workspace.  (a.k.a. "store/hide something secretly somewhere")
暫存未 commit 的內容到 stash 中

git stash

git stash -p #support --patch

Stash only staged files

git add app/controllers/cart_controller.php

git stash --keep-index

git reset

Restore (without popping out)

git stash apply (--index <?>)

Pop out

git stash pop

-----

Check out a remote branch as a local branch
開一個 local 分支，內容是 remote 分支：

git checkout -b LocalName origin/remotebranchname

----

# rewrite history (change previous commits)

git rebase -i HEAD~3     # use last 3 commits as an example

# rewrite history (amend last commit)

git commit --amend

# go back to previous commit (with a new commit)

git revert --no-commit 0766c053..HEAD

git commit

# move HEAD to previous commit then push to server

# (note: it rewrites history, generally not good, git revert might be better)

git reset --hard 0d1d7fc32

git push --force

----

# rename local branch / remote branch

git branch -m <old_name> OR

git branch -m <old_name> <new_name> OR

git push origin :<old-name> <new-name> (delete remote old-name branch and push local new-name branch)

# remove / delete local branch

git branch -d <branch name>

# remove / delete remote branch

git push <remote_name> --delete <branch_name>

git push <remote_name> :<branch_name>

#force update the remote branch list

git remote update origin --prune OR

git pull -p

# force push the local branch to remote (ignoring the remote status)

git push origin --force

----

# show abbreviated commit hash (short hash)

git log -1 --abbrev-commit

# remove all branches named with chriz.chow

git branch -r --list "*chriz.chow*" | sed 's/origin\///' | xargs git push origin --delete

----

Sometimes if you want to checkout a branch (e.g. dpp), but you also have a file called dpp.
When you run "git checkout dpp", Git does not know what operation you want.

To switch to dpp branch, you can run:

git switch dpp

To restore the dpp file, you can run:

git restore dpp

Alternatively, you can also add double-dash to indicate it is a file path:

git checkout dpp --