顯示具有 學習筆記 標籤的文章。 顯示所有文章
顯示具有 學習筆記 標籤的文章。 顯示所有文章

2015年4月8日 星期三

計算機組織 - 電腦概述


摩爾定律

每隔18~24個月,積體電路上可容納的電晶體個數便會增加一倍。
 

電腦系統的種類
  • 桌上型電腦(Desktop computers):一般泛用的個人電腦。
  • 伺服器型電腦(Server computers):涉及網路,追求高效能、高容量及高穩定性。
  • 嵌入式電腦(Embedded computers):嵌入於其他系統(如手機、電視)中的電腦,追求耗電與效能之間的平衡。


程式的處理階層:


軟體層面(Software):
應用程式(Application software):為了達成特定需求(如遊戲、圖片\影片編輯......等等),由高階語言編成的軟體。
系統軟體(System software) :負責管理及協調硬體階層,包括了作業系統及編譯器等等。
硬體層面(Hardware):
囊括了處理器、記憶體,以及IO控制器等等。

程式語言的階層:

高階語言(High level language):
貼近人類語言,容易閱讀及編寫,透過編譯器或直譯器轉換為機器碼。
組合語言(Assembly language):
屬於低階語言,指令多與處理器直接對應,以文字來描述機器的行為,透過組譯器轉換為機械碼。
機器碼(Machine code):
由0和1構成的處理器的指令集,電腦可以直接識別。

電腦的元件:

不論是嵌入式、伺服器,或是桌上型電腦,都包含了這5個主要部分:
  • 輸入與輸出元件
  • 記憶元件
  • 控制元件
  • 資料路徑(Data path)

效能評估

Response Time and Throughput


  •  Response Time(反應時間)
又稱為elapsed time,表示要完成一件工作所需花費的時間。其中包括了CPU time、I/O、OS overhead及閒置時間。
  •  Throughput(生產能力):在一定時間內所能完成的工作量

CPU time


即CPU處理給定的工作所花費的時間,可再細分為User CPU time(處理器在處理這分工作所花的時間)與System CPU time(作業系統為了執行這份工作額外的準備時間)
CPU time 可以這麼定義:

CPU Time = CPU Clock Cycles * Clock Cycle Time
= CPU Clock Cycles / Clock Rate

Clock cycle稱為時脈週期,時脈(Clock)就像電腦中的一個計數器,每當時脈走了一格,便是完成了一個時脈周期,而走這一格所花費的時間,即是Clock Cycle Time,因此CPU Time即是總共走了幾個時脈周期乘上每走一個時脈周期所要花費的時間。

因此,若要改善CPU Time,我們能從減少clock cycle,或是增加Clock Rate著手。

CPI


CPI (Cycle per instruction) ,表示每執行一個指令(Instruction),所要花費的時脈周期
Clock Cycles =  Sigma(CPIi * Instruction Counti ),i from 1 to n.
Average CPI  = Clock Cycles/Instruction count

指令的個數由編譯器、ISA(ISA instruction set architecture)、程式與演算法共同決定。

CPU Power


Power = Capacitive load * Voltage2 * Frequency

設計要追求高響應(Frequency)而低功耗(Power),便須下調前兩者的影響,然而在2004年後,降低電壓與冷卻的技術飽和而停滯,在功率挑戰中形同撞上了一面高牆(Power wall),為了執續強化處理器的效能,技術便轉往多核心發展。


然而純粹增加核心數並不完全相關於效能改善,即是說「在單核心中要執行100s的工作,在五核心的電腦並不會只要執行20s」,實際上,它要花費 36 秒,這個數字是由阿姆達爾定律所推得(80/5 + 20 = 36),阿姆達爾闡明了:即便無限的增加處理器的個數,仍然存在一個加速上限。

2014年12月9日 星期二

數位簽章

Digital Signature



什麼是數位簽章:
  • 數學演算法或其他運算方式,對要簽署的文件進行加密,所產生的結果
數位簽章的需求:
  • 驗證
    • 簽章者身份 (不可偽冒)
    • 簽章日期、時間
    • 訊息完整性 (不可偽造)
  • 透過此簽章,能讓第三方來解決紛爭 (不可否認性)
 數位簽章流程:
  • 產生簽章
    • 有一份文件M 
    • 計算文件的摘要 H(M),明文中1bit的不同,會在摘要產生大量不同  
    • 加密摘要:Ek(h)
    • 獲得簽章 S = Ek(h)
  • 同時傳送M與S給對方,完成簽章的傳送
  • 接收方也有一把驗證金鑰,可以對文件與簽章進行比對,確認這個簽確實是對應這份文件
  • 注意:簽章屬於非對稱式金鑰
    • 為什麼要是非對稱?
      • 若為對稱式金鑰,接收方可用同樣方式產生出簽章來仿冒傳送人
    • 加密用的是私鑰,解密用的是公鑰
    • 也就是說,簽章的結果是所有人都可以比對的
      • 有利於第三方驗證

2014年12月8日 星期一

組合邏輯電路

1.組合電路 v.s 循序電路
  • 組合電路:
    • 由邏輯閘構成,輸出為當前運算的結果
  • 循序電路:
    • 使用了儲存原件與邏輯閘
    • 輸出關係到輸入與先前儲存的結果
2.組合電路設計順序
  • 確定問題
  • 確定輸入與輸出
  • 指派輸入與輸出變數
  • 推導真值表
  • 簡化布林函式
  • 繪製邏輯電路圖並驗證結果
3.加法器
  • 半加器:2輸入2輸出,兩個當前要相加的bit,輸出該位元相加值與進位值
  • 全加器:3輸入2輸出,兩個當前要相加的bit,一個為前個bit的進位 ,輸出該位元相加值與進位值 
  • 透過串連的全加器,可夠成N-bit的加法器(漣波進位加法器)
    • 跟直觀的人為加法一樣,由後往前加,所以必須知道前一個bit是否有進位才可繼續運算 →造成傳遞延遲
  • 為了避免漣波進位的延遲 → 超前進位加法器
    • 因電路複雜使成本增加,但是簡短了運算時間
    • 打破資料相依性,使相加結果只與C0(初始值)有關
      • 使用疊代,將目前進位以前一次相加的結果取代,始終用最低位元表示
      • 因此,越高層(高bit)的電路,複雜度會愈趨增加
  • 使用加法器實做減法器
    • 可以透過一個位元操作
    • 減法其實等於與2補數相加,而2補數為1補數再加1
    • 那麼
      • 有AB兩數
      • 透過一個位元M,傳給C0,先將與B的各個Bit與M做Xor再送入全加器
      • 當M = 0時,B xor M = B,C0 = 0,為加法
      • 當M = 1時,B xor M = B',C0 = 1,所得為B的1補數+1=B的2補數,為減法
4. 溢位
  • 定義:一個n-bits間的運算卻造成了n+1-bits的結果 → 進位到了表示正負號的bit
  • 電腦必須偵測溢位並設置正反器以供之後調用
  • 如何避免溢位?
    • 假設有7bits相加
    • 使用9bits去儲存,多的2個bit
      • 第9 bit當作正負號
      • 第8 bit當做額外進位(7→8)
5.比較器
  • 兩輸入:A、B,三輸出:A>B、A<B、A=B 
  • 假設A、B的為4bits:A3A2A1A0、B3B2B1B0
  • 令Xi = AiBi + Ai'Bi' (Ai XNOR Bi)、即Ai、Bi相同時為1
  • 當A = B →  A3 = B3(X3 = 1) ...... A0 = B0(X0 = 1) → A=B可以表示為 X3*X2*X1*X0
  • 判斷A > B:A3B3'+x3A2B2'+x3x2A1B1'+x3x2x1 A0B0'
    • 先看A3B3'
      • 如果A3是1、B3是1:該項為0 → 往下一bit繼續比
      • 如果A3是1、B3是0:該項為1 → 不用比了,A > B
      • 如果A3是0、B3是1:該項為0,而且x3為0 → 接下來的每項都 = 0 → A < B
      • 如果A3是0、B3是0:該項為0、不過x3為1 → 可以往下一bit繼續比
    •  可以發現x3、x2...可以用做比較是否進行的標準
  • 判斷A < B:A3'B3+x3A2'B2+x3x2A1'B1+x3x2x1 A0'B0
6.n to m 解碼器
  • 有 n 個 bits→ 能表示 2^n種情形
    • 解碼器目的:輸入有n bits,產生2^n種輸出 
    • 即是表現出所有的 minterm 型式
    • 既然能表示出所有的 minterm,即能利用解碼器實做出任何電路
      • 但是效率並非最佳化
7.編碼器
  • 解碼器的逆操作: 2^n → n
  • 無法用卡諾圖化簡,直接用結果畫電路
  • 優先權編碼器
    • 允許多個輸入為1,因為只看最高位元,其他為Don't care (X)
8.多工器 (選擇器)
  • 目的:從多個輸入中,選擇出其中一個輸入
    • 比如說有輸入A、B,選擇用位元S
      • 使 A AND S、B AND S',再將他們做 OR
      • 在 S = 0時,輸出的是 B
      • 在 S = 1時,輸出的是 A
9.三態閘
  • 輸出:0、1、高阻抗(斷開電路,不會產生邏輯訊號)

2014年11月20日 星期四

OpenStreetMap

講者:李昕迪 mcdlee


  • 想像自己是一個地圖廠商老闆
    • 收集一個城市或國家的資料,應當耗費多少資源?
    • 自己又要花費多少的比例,在收集這些資料
      • 多久更新一份資料?
      • 多久能處理一份Bug?
  • OpenStreeMap (中譯為開放街圖)
2004年由Steve Coast成立,具備Open Source與Wikipedia的精神,屬於開放授權(ODbl)且開放格式(對外交換為xml),只要有標註來源,就可以自由的複製、散布、傳輸與修改。

OpenStreetMap包含了森羅萬象的地理資料庫,如路網、地名、設施、速限、甚至連路燈、涼亭、店家開門時間等等都有標註,也可挑選其中幾個屬性作為其他地圖的底圖使用,比如素食地圖、WheelmapFOURSQUAREOpenHistoricalMap(歷史地圖數位化)等等。
  • Mapper(圖客)
開放街圖的貢獻者,帶著GPS的tracker,或透過Field Papers印製地圖,實地走訪在圖上描點,紀錄完資訊後上傳至開放街圖。
  • WikiStyle
    • 可能發生悲劇(惡意修改),但紀錄有跡可循
    • 半成品是可接受的,因為每個人都可以編輯


2014年11月13日 星期四

軟體的國際化與在地化

自由軟體開發與社群發展

講者:FrankLin


INDEX Topic 1.自由軟體的國際化與在地化
Topic 2.Ezgo打包的技術初窺探

講者介紹:
Franklin,在社群中被稱為馬哥,大一開始玩Linux,但真正栽入Linux與OOS是在念研究所時。出社會後都在做RD,現在則是以OSS為業的浪人。
2006年起,擔任KDE中文化團隊的協調人。

Topic 1.自由軟體的國際化與在地化


 Ezgo是推廣自由軟體用的一個系統,既然要推廣,中文化就是個相當重要的部分。
  • 國際化與在地化
過去的軟體,光是要能顯示中文,就要處理很多事情,如訊息的顯示、字型(px上的設定,同時涉及了自行的解析度)、編碼問題,使得在過去中文版的推出,即是一件大事。

而除了訊息,還可能會涉及當地的觀念,像是:
  • 數字表示法
例如在歐洲大多數的國家,1.000是一千,1,000才代表1,假設今天有一個德國的會計軟體,台灣中文化就得做內部的修改。
  • 年份的表示法
  • 日期的表示法
  • 金錢的表示法
  • 度量衡系統
這些都是在軟體在地化時要做的處理。

而現在,為了在同款軟體賣給不同國家時不大量修改,軟體公司提出簡單多國語言化概念。

原始程式→將訊息抽取出來編索引,存成一個檔案→將該檔的內容翻成不同語言
(原始程式在設計時就該有能檢視索引的機制)
因為訊息已經抽出來了,所以只要針對訊息獨立處理,不必修改原始程式。

Linux 上的中文化始祖 - CLE


Chinese Linux Extension - Linux 中文延伸套件
延伸:修改程式內容,重新編譯打包,以加入中文支援

CLE團隊也知道,光是修改打包只治標而不治本,因此積極與原始Linux團隊合作,期望加入國際化軟體的架構。
包刮 Linux ,  glibc , QT, KDE ,Gnome......都從收過CLE團隊的修改。

所謂國際化,即是將軟體與特定地區及語言脫鉤的過程,當移植時,不必做內部工程上的大量改變或修正。而在地化便是延續國際化的架構,建立某個地區文化的資料庫,填入該地區文化的資料,供程式在執行期呈現。

Gettext


關於自由軟體的國際化,主要是靠著Gettext這套軟體進行,Gettext只是套工具,他利用對訊息的包裝,可以將訊息抽取出來集中在一個 .pot 檔,翻譯者只需要拿pot翻譯成不同語言,並各別存成po檔即可,而開發者會將po檔編索引成為mo檔。

po檔分為檔頭與條目:

  • 檔頭存放的是po檔與其相對的pot檔的相關資訊,包括產生時間、最後翻譯者,還有複數型的定義 (plural - form)。
  • 條目則分為旗標與註解(區別相同訊息但不同意義,e.g: left : leave過去式? 左? )

翻譯工具簡介


  • 翻譯資料庫
  • Launchpad、pootle、transifex、tryneeds等線上共筆的翻譯平台

Ezgo打包技術初窺探


  • What is ezgo
    • 能夠讓從未接觸過OSS的人,接觸OSS並使用它 → 推廣
  • 推廣
    • 目標客群:從未用過OSS的人
    • Ezgo該有哪些特色?
      • 選單
      • 操作設計上貼近Windows思維
  • 從技術面而言
    • 屬於客製化的distribution
      • 有自己的品牌,卻不是一個獨立的distribution
    • Dirty hack產生的問題
      • 沒有組織,東西太零散
      • 版本一多不易管理
      • 不符合Debian規範,無法上傳
    • 目前的做法
      • 儘可能遵循標準機制,並自動化
      • 儘可能採用外加設定檔的方式,不覆蓋現有檔案
  • Debian - ezgo
    • Debian:套件的老祖宗
    • 遵循Debian規範,將常用重複的檔案與設定等等包裝成deb檔

2014年11月9日 星期日

Network Security issues

  • Network Security Basis
    • Confidentiality
      • 維持資料的完整性
    • Integrity
      • 確認資料是否有被修改
    • Authentication
      • 建立使用者身份的認證
    • Non - repudiation
      • 防止使用者否認其曾做過的行為
    • Access Control
      • 管制使用資料的使用權限
    • Availability
      • 隨時保持資料的可用性
  • Protocol
    • 網路傳輸的協定:HTTP/FTP......
    • 資訊安全的協定:SSL,IPSec,Kerberos......
  • Ideal Security Protocol
    • 滿足安全需求
    • 效率高
      • 運算量少、延遲短
    • 健壯性
    • 容易使用與實作且應用彈性高
  • Secure Entry to NSA
    • Insert badge into reader
    • Enter Pin
    • Correct Pin?
      • Yes : Enter
      • No : get shot by security guard

Authentication Protocol

  • mutual authentication
    • 假設現在有兩個使用者Alice和Bob (可以為人或電腦)
      • Alice必須要向Bob證明她的身份是Alice
      • 同樣的,Bob需要向Alice證明他的身份是Bob
      • 因為雙方都要驗證自己的身份,而稱為mutual authentication
    • 過程可能需要建立對稱金鑰,作為辨別的基準
    • 雙向認證的必要性
      • 以往都只有系統認證人
      • 但人遇上假的系統 → 資料外流
  •  Challenge-Response mode
    • 為了避免重放攻擊,使用challenge-Responce
    • 當認證時,使用只有Alice本人才能進行的認證
    • e.g.
      • Bob為了確認Alice的身份,Bob送出一個Nonce給Alice,Nonce就是個Challenge
      • Alice對 Alice's password跟Nonce進行一次雜湊
        • 因為只有Alice跟Bob知道Alice's password,所以可避免重放攻擊
      • 若Bob進行雜湊的結果與Alice一樣,就能確認Alice的身份
  • Authentication : Symmetric Key
    • Alice和Bob共享一把對稱金鑰
    • 只有Alice和Bob知道這把金鑰
      • 為了認證Alice的身份,Bob會傳送一個Nonce,給Alice
      • Alice對Nonce進行加密 E= (Nonce,key),傳送E給Bob
      • 上述只完成了Bob對Alice的認證
    • 那麼如何完成雙向認證呢?
      • Alice先送Ra給Bob
      • Bob送回Rb跟E(Ra,key)給Alice
        • Alice可透過解密知道是否為Ra
      • Alice送出E(Rb,k)給Bob
        • Bob可透過解密知道是否為Rb
    • 然而,這會產生一個問題
      • 分成兩次的嘗試
      • 第一次,攻擊者可以透過送出Ra得到Rb跟E(Ra,k)
      • 第二次,攻擊者送出Rb,得到E(Rb,k)
      • 那麼就可以在第一次嘗試中送回E(Rb,k) 
  •  

2014年11月6日 星期四

Ezgo

Ezgo

Speaker : Eric


Ezgo開源教材分享
  • Stellarium
    • 可以描繪星體的軌跡
  • MuseScore
    • 可繪製五線譜,快速調整譜面
    • 可隨音符演奏音樂
    • 配有音樂社群,分享音樂創作
  • Hydrogen
    • 節奏編曲軟體
    • 配有各種音源,操作容易
  • Fritzing
    • 備有虛擬麵包板與圖像化電路,可以用於電路設計上的教學

2014年11月4日 星期二

C4 Labs Course 4

#1. Makefile


  • makefile REF
    • Makefile學習筆記
  • 平常的編譯方式
    • gcc file.c -o file
    • make file.o -> make file
  • makefile :很多個檔案要做編譯,彼此之間有相依性,所以寫一個腳本來完成所有的編譯動作
PROJECT = test
OBJS = a.o b.o c.o //物件檔當成三個字串

all: $(PROJECT)
$(PROJECT): $(OBJS)
...編譯指令...
  • 檢查include的標頭檔是否有被改過
    • 知道誰被改過,又有誰用到它
  • 建立一個描述相依性的檔案,然後將其include到makefile中
    • command line指令:-MF
      •  產生出一個.d檔,說明完成這個.o檔需要哪些.h檔
  • 引入一個目錄內所有檔案:wildcard
    • wildcard會展開目錄內的檔案

#2.Arch Linux


2014年10月31日 星期五

鳥哥的私房菜&國際社群參與

#1.鳥哥、鳥站與自由軟體的學習
講者:鳥哥


  • 自我介紹(?)
    • 菜鳥長大了,總該變成哥
  • 為何接觸Linux
    • 一開始是被環境所逼
      • 不過換個想法,多學學也是件好事
    • 以前的信箱都有流量限制,所以想架設mail Server給自己使用
  • 為什麼會有鳥站
    • 因為想輕鬆一點
      • 為了要讓更多學弟妹學會linux,老師就不會老是找我了
    • 所以鳥站的來源其實是
      • 預防忘記以前做過的蠢事,以防再遇上時又要花時間
    • 鳥站怎麼來的
      • 從study area跟bbs.sayya.org(已關站)學習網路、電腦及Linux的基礎
        • 內容難度較高
      • 鳥哥創造Linux.vbird.org
        • 較適合新手入門
  • 關於鳥站?
    • 一開始會引起注意的主因是鳥哥夠雞婆
      • 解決討論區上看到的各種特殊問題
    • 鳥哥有句名言:我沒有錢
      • 因為沒有錢,設備買不起,只好用點特殊方法取代
      • 所以,就得要學習一些比較特殊的技巧
        • 這其實也是件好事
  • 鳥書?
    • 鳥站的文章一定比書籍還要新
  • 近年鳥哥在玩的東西
    • 教學專用虛擬化平台
      • 起因:沒linux要教linux
      • 遇上的問題:
      • VM效能優化
        • 透過Red hat Spice
      • VM Cpu優化
        • 原先使用的是最陽春的CPU
        • 改成透過libvirt的CPU去修改
      • 對顯卡負擔較重的軟體無法使用
    • 既然有實體PC/電腦教室了,為何還需要雲端?
      • 比較省錢

#2.參與國際社群經驗談
講者:Max

Slide

2014年10月29日 星期三

Linked list - 鍊表



1.Why Linked list ?
因為Array在使用上存在兩個問題
  1. 在宣告時,就得指定大小,如果分配太多會造成空間的浪費,若分配太少又會出現錯誤,
  2. 若要刪除或插入某個元素至陣列中,通常須對其他元素進行平移
而Linked list能透過pointer動態的分配紀憶體空間,補足了Array這兩個缺點。

2. Linked list的核心人物:pointer
  • Pointer存放的是記憶體位置
  • & : the address operator (對一個變數取得它的位置
  • *  : the de-referencing operator (這個變數的位置去取得它的值
  • e.g. :int * p = &x;
    • int * p  :宣告一個儲存int位置的pointer
    • p = &x :讓p儲存x的地址
    • 而*p形同*&x,對x的位置取值,自然能取得x的值囉
  • 誤用Pointer
    • Dangling pointer
      • pointer記錄到失效的記憶體位置(比如已經被刪除的變數),進而取到錯誤的值
    • Memory leakage
      • 忘了去deallocate不必要用的空間
3.Linked list
  • Singly linked list
    • 結構 :
      • 一個pointer的欄位,指向下一個節點(node)
      • 一個data的欄位,儲存這個節點的資料
      • 通常我們會用一個指標Head來指向第一個節點
      • 通常最後一個節點會指向NULL
    • 對linked的操作
      • 1.定義一個節點的結構(struct)
      • 2.當要新增一個節點時
        • 先分配記憶體給這個新節點
        • 把list中最尾端節點的指標指向新節點
      • 3.當要移除一個節點時 -> free

2014年10月23日 星期四

g0v & Git Cafe

Topic #1 g0v零時政府 & open data

講者:江明宗

一、簡介g0v與open data

  • g0v -> 為了補足gov的不足而成立

    • g0v 社群 motto :「不要問為什麼沒有人這個?先承認你就是『沒有人』,因為『沒有人』是萬能的!」

  • open data 的五個等級

    • 1.open licence : 開放文件的存取
    • 2.RE : 提供的文件可再使用/修改
    • 3.CSV : 純文字開放格式
    • 4.Url : 有固定的網址存放資料
    • 5.Ld : 除了自己的資料,還能跟別人的資料連結在一起

二、g0v專案

  • Case 1:開放政治獻金
    • 起因:監察院的資料必須到場查閱
    • 2013開始
      • 進監察院取得紙本資料,再將其掃描成電子檔
      • 因為圖片幫助不大,考慮用openCV按照掃描完成的表格切割
      • 工程師設計出一個網站,用來比照文字與圖片
    • 2014/04/19 專案正式公開
      • 24小時內,完成7個專戶,共309,666個文字比對
    • 截至目前,取得了28個專戶資料,但仍只是冰山一角(監察院有約6000個專戶)
    • 未來展望:將公司之間的投資關係畫做關聯圖,以釐清政治人物與企業之間的關係
  • Case 2:
    • 政府的選舉公報在2天前才會發出
      • ->要在 2 天內看完十餘名的候選人的資料
    • 減少盲目投票,讓民主社會的台灣更進步
      • 所以我們成立了一個網站,匯入村里等行政區以及選舉資料庫的資料,羅列出所有候選人的政見,並透過tag分隔出政黨、選區等等
    • 在Hackpad上線上編輯
      • 發佈想要整理的格式,轉發至ptt、FB
    • 運用newsdiff資料取得候選人相關新聞,並且將其比對
    • 2014/7月時,GitHub開始有人傳送PR
    • 2014/9月,匯入中選會登記概況

Topic #2 Git Cafe

講者:林旅強 Legist Qiang

一、Git Cafe與Git
  • 代碼託管 + Open Source 協作平台
  • 版本控制:
    • 對修改留下log,可以輕易知道改了什麼以及回復先前的文本
    • Git就是一個多人版本控制系統
      • 分散式,每個人的本機端都有一種套的版本
二、Open Source
to understand the concept you should think of free as in free speech not as in free beer -Richard Stallman
  • Free software foundation
  • GNU project (GNU's not Unix)
  • 自由軟體定義
    • 有使用程式的自由
    • 有修改程式的自由
    • 有再散播程式的自由 
  • Free Software -> Open Source
    • 因為free自由總是被誤解成免費
    • The Cathedral and the Bazaar
      • Open Source之所以好,因為它的選擇性很高,就像一個市集。
      • 蓋教堂是種開發模式,而市集又是一種開發模式
  • Creative Commons
  • Community & Crowdsourcing
    • e.g. PTT 成為納莉颱風第一手訊息流通處 
三、Open Source與個人發展\
  • 把自己的code放上平台,會有自己與助教之外的人給予建議
  • 參與開源專案,發掘自己真正的興趣
  • 遇到問題,通常會去問有經驗的人,社群在業界與學界都有相當好的資源
四、如何參與社群
  • 國際社群
    • e.g. Linux Kernel,Debian,Ubuntu,Gnome...

2014年10月19日 星期日

區塊加密的工作模式

1.當message size大於或小於加密的block size時,我們通常會將其切割:
  • 比如在AES的情形下,容許一次加密的明文為128bits,那我們必須先把加密文件切割成若干個128 bits 才能進行加密處理。
2.為什麼我們需要引入各種加密型式
  • 將加密算法配合至各種需要(如上述第一個情形),同時也能增加密文的強度
3.ㄧ些常見的塊密碼工作模式
  • ECB : Electric Codebook
    • Let Plain text to P1,P2,P3,...Pn
    • Let Cipher text  to C1,C2,C3,...Cn
    • 把明文分成若干的block,各自加密,或將密文分成若干的block,各自解密
    • 弱點:重複的block + 重複的Key → 重複的密文,面對頻率分析相當危險
      • 比如加密星期二寄出的Email,Tuesday重複被加密成同樣的密文
      • 重複觀察就知道,這都是禮拜二寄出的,可以借此解出金鑰
  • CBC:Cipher Block Chaining
    • 一樣把明文分成若干塊
    • 把目前明文跟前份密文做Xor,之後再將完成Xor的明文送入加密演算法
    • 第一份明文需要一個初始向量(Initial Vector)做Xor
    • 限制:
        • Bit Flipping Attack
          • 因為傳送中有一點缺失,密文將大量改變 -> DoS
        • 需要一個IV,要讓sender and receiver 知道且不可重複

上述模式在明文被分割成若干區塊前不可執行,需要補綴處理至區塊大小
接下來的模型將明文當作位元流,可以對即時的資料進行加密

  • CFB:

    • 將明文視為位元流
      • 首先將明文切割為兩部分b-s與s
      • 將明文加密,捨棄b-s的明文,將s部分的密文與前一部份的s明文Xor得密文C
      • 把新明文左移s位,插入C至新明文
    • 限制:
      • 會有延遲,無法併行處理資料
      • 跟CBC mode一樣,錯誤容易擴散
      • 那麼,有偵測錯的方法嗎?
        • 可以加入除錯碼,可以及時發現錯誤,但要犧牲一個bit
        • PCBC mode
  • OFB:
    • 同樣的,把明文作為位元流
    •  一開始加密一個初始向量
      • 將加密後的初始向量分別傳到:
        • 1.第二個block
        • 2.與P1做Xor -> 得密文C1
      • 再來對先前傳至第二個block的IV做加密,完成後分別傳到第3個block ......
    • 優點:
      • 不依賴產生出的P1或C1, 所以不產生時間延遲
      • 錯誤不會擴散
  • CTR (Counter):
    • 加密方法:將Counter i 加密,與Pi進行Xor得到密文Ci,持續進行直到完全加密
    • 解密方法:將Counter i 加密,與Ci進行Xor得到明文Pi,持續進行直到完全解密
    • 每進行一次運算,便會將Counter++,所以稱為計數器模式
    • Counter 不應該被重複使用,避免相同明文出現相同密文
    • 類似於ECB的觀念,但放入加密器的是會變動Counter,而且Counter總是128位,所以可以視作密鑰流處理

  • 確保資料的正確性
    • message authentication
      • CBC - Residue, or CMAC , NMAC
      • HMAC
    • 核心觀念:建立一個除錯碼以及演算出除錯碼的方式,由傳送方跟接收方約定而成,接收方在獲得密文後再進行驗證。

2014年10月16日 星期四

自由軟體 - 台南數位文創園區

台南數位文創園區

講者 : AJ


  • 園區提供設備
    • 3D印表機
    • 雷射切割機
      • Tinkercad
        • 線上建模網站
        • 使用OpenGL,所以不支援IE
  • PanScience泛科學
  • 台灣第一大科普網路社群
    • 用輕鬆有趣的方式,推廣科普閱讀
  • Npost公益交流站
    • 關注主流媒體不關注的公益問題
    • 讓公益變成全民運動
 it's technology married with liberal arts, married with the humanities, that yields us the result that makes our heart sing
協會的初衷:科技應當與人結合,與人作互動。我們一開始就是使用PunCar把自己送進任何需要我們的地方,教導他人Excel、Google、Dropbox,用最簡單的方式,去替不會使用電腦的人解決問題,而在我們離開那裏後,改變仍能留下,讓科技與當地人結合,進而改變他們的生活。同時這也是增長自身經歷的過程,能從不會使用電腦的人的思考模式出發,換個不同的邏輯或許也會有不同的發現。

台南數位文創園區與政府合作,為任何想創業的人,想自己做小物品的人,想參與活動的人,提供空間與設備讓大家互相認識,同時也會邀請一些創業家來演講,讓每個人都有學習與分享的機會。

Queue - 佇列

Queue跟Stack一樣都是有順序性的,存與取之間有一定的規則。直觀來看,Queue其實就像隊列,排頭的當然先服務,後到的就得等前面完事才能往前走,當然,我們不考慮插隊的情形,每次要加入這個隊伍的,都必須排在隊伍尾端,所以成了FIFO(First in First out)的型式。

1.Queue ADT
  • Queue CreatQ(maxQueueSize) :創造一個空的quene
  • Boolen IsFull(quene,maxQueuesize):判斷quene是否滿了,
  • Boolen isEmpty(queue):判斷quene是否為空
  • Quene Add(queue,item):添入item是quene
  • Element Delete(queue):刪除quene中的一個物件,並把它傳回給item
Queue的操作都與Stack類似,主要有兩個不同:

其一是stack有一方是底,我們只需要一直把東西丟進去丟進去,不過quene則是兩端皆開放的,要分別處理排頭跟排尾,所以我們需要兩個變數(front , rear)來儲存quene的頭跟尾,而front與rear的初始值一樣可以當作-1,配合於isEmpty的判斷上。
  • add : rear = rear +1
  • delete : front = front +1;
第一,從上述的操作,我們可以看出quene會不斷地往右偏移,所以在判斷isFull時,我們不能僅考慮rear是否>maxQuenesize,我們要思考的是,這個隊列是不是真的滿了?如果沒滿,則要把整個隊列往左平移。

2.Circular Queue

它是一個環狀的queue,這能解決上述第二個問題,不過他也得付出一點代價,即只能放MAX_Queue_Size - 1個元素,剩下一個必須用來判斷queue為空或為滿。

3.其他quene形式
    • Double ended queue:兩端都能放且兩端都能拿的queue
    • Priority queue:元素在queue的位置跟它的priority值有關,跟進入queue的時間無關
    • Double ended priority queue

Stack 堆疊

1.什麼是Stack?

如果把input的資料當成積木,Stack就像疊積木一樣,把新加入的磚塊放在後加入的上面,要拿出也是把新加入的拿出,屬於LIFO (Last - in -First out)模型。

2. System Stack

有些語言函式的呼叫也是個Stack,比如Function A呼叫了Function B,而Function B又呼叫了Function C,用Stack結構來表示的話:

FunctionC
FunctionB
FunctionA

FunctionC會先執行,完成後才會是B與A。
當然囉,如果函式巢狀增加,這些積木也會越疊越高,而高度也是有個極限的,當到某個地步後還要疊的話,就會發生stack overflow的情形,所以在Recursive的終止條件上要特別注意。


4.Stack 的抽象資料結構
  • Stack CreateS(maxStackSize) :創造一個空Stack,並給予這個Stack最大容許儲存量
  • Boolean IsFull(stack, maxStackSize):確認stack是否滿了,避免push時把item丟入錯誤區塊
  • Boolean IsEmpty(stack):確認stack是否為空,避免pop時丟出的錯誤資料
  • Stack Push(stack,item):配合isFull使用,當還有位置放時,把item放入stack
  • Element Pop(stack):配合isEmpty使用,當裡頭還有物件,就把物件丟給item
實作stack最簡單的方法就是用一維陣列去處理它,為此我們需要兩個東西,一個是陣列stack[MAX_SIZE]來儲存,另一個就是top,用來表示目前存了多少item。

top
...
...
Stack[2]
Stack[1]
Stack[0]

在創造一個Stack時,可以把top設為一個非合理範圍,比如 -1,這樣便可在isEmpty上做判斷。
每當push就top++,如果top合理,便加入物件,pop則把top--,丟出物件。

5.一些Stack的應用

System Stack就是堆疊的基本應用,他用於在Run-time時決定Function呼叫的順序。在進行Backtracking與Recursive上,也涉及了Stack的概念。








2014年10月13日 星期一

卡諾圖的化簡

1.認識 minterm & maxterm

Minterm   :  由輸入或輸入的補數構成的   AND
    比如有兩個輸入x,y,那minterm = xy , x’y, xy’ ,x’y’
Maxterm : 由輸入或輸入的補數構成的    Or
    比如有兩個輸入x,y,那maxterm = x + y, x’+y , x+y’ , x’+y’

->考慮DeMorgan’s theorem
    (A + B + C)’ = A’B’C’
    (ABC)’ = A’ + B’ + C’

可以進行Minterm與Maxterm之間的轉換:
    e.g. x’y’z’ = m0 = x + y + z =M0
再比如說有一個電路
    F = x’y’z’ + xy’z’ + xyz = m1 + m4 + m7,
    F’ = x’y’z’ + x’yz +x’yz’ +xy’z +xyz’ =m0 + m2 +m3 +m5 +m6
    F’’ = (x+y+z)(x+y’+z)(x+y’+z’)(x’yz’)(x’y’z)
所以說F可表達成兩個形式

    1.  5個 minterm    or   在一起 (SOP)sum of product形式
    2.  5個 Maxterm  and 在一起 (POS)product of sum形式


那有了Minterm跟Maxterm有什麼好處呢?

    若電路F表示為 x’y’z + xyz +xyz’
    上述的F稱為 canonical form,因為它有三個輸入,而且每項都有3個變數,實際上F可化簡為x’y’z +xy,但這樣就非 canonical form
    那表示成canonical form又有什麼好處?就是真值表定可表達成canonical form,比如說:
        x=0,y=0,z=1,可以寫作x’y’z
        x=0,y=1,z=1,可以寫作x’yz
        x=1,y=1,z=0,可以寫作xyz’
    所以只要有真值表,任何電路總能表達成canoncial form(SOP或POS),但是這個形式有個致命的缺點,就是他的變數很多,這間接導致了成本增加。

於是,我們需要簡化的技巧

Gate-level minimization

2.Karnaugh Map

    1.按照格雷碼填入電路輸入 e.g(00 , 01, 11, 10)
    2.圈1 or 圈 0 ,以1,2,4,8,16,32...2的次方為個數去圈,儘量多圈讓化簡達到最大效果
    3.圖視為連通的
    4.持續的圈0 or 圈1,直到所有的0或1都被圈到
    5.圈1得到化簡的F (SOP形式),圈0得化簡的F' (SOP形式),需再做一次迪摩根得F(POS形式)
   
0或1可以重複圈,但是一定要完全圈完其中一種
注意:如果一個項的變數個數跟輸入不同,比如說輸入有w,x,y,z,但F中有一項為wxy’,即缺少了z項,那麼我們就要把wxy’z與wxy’z都視為1

卡諾圖的消去原理:(x' + x) = 1

2014年10月12日 星期日

串流加密法

串流加密法


像DES、AES這種將明文分為一個一個區塊(block)的稱為區塊加密,與之區隔的便是串流加密。

串流加密的精神在無論明文或是金鑰,都將其視為位元流來操作,如此一來,就不必特意去分割明文區塊,在需要處理即時資料時相當方便。
  • 區塊加密
    • DES (Data Encryption Standard)
    • AES (Advanced Encryption Standard)
  • 串流加密
    • 亂數產生器
    • A5/1
1.亂數產生器
  • 可以視為一個實際版的One - time - Pad
  • 線性反饋移位暫存器 (Linear Feedback Shift Register)
    • 移位暫存器越長安全性越高
    • 理論上 L = n 之LFSR最多可產生2^n-1的週期
      • 要為Primitive polynomial(無法再分解成2個多項式的乘積)
  • A5/1
    • 利用3個LFSR (19bits 22bits 23bits)
      • 為什麼長度要不同?
        • 因為一開始LFSR都是為0,必須要透過一個64bit的key填入,LFSR長度必須不同,初始狀態才會不同
    • 填入LFSR後再將LFSR初始狀態分別作22跟100次的打亂
    • 總是反饋最大的值
      • e.g. = maj(x3,y4,z4) = (1,1,0) = 1 (因為1有兩個)
        • 於是x3 -> x4 , y4 ->y5 ,z4不動
    • A5/1 Demo

現代加密 - AES

AES



1.AES根據金鑰長度不同分別有10、12、14個回合,每個回合各有一把128位元的金鑰

2.明文區塊(block)與狀態(state) 上的轉換
  • 將明文block轉換為16進位編碼,填入矩陣(State)
  • 同樣的,每把鑰匙也能用state表示
  • State為16進位的數字
3.操作
  • 1.SubBytes : 假設state是19,則找第一列,第九行,取代state
  • 2.Shiftrow :第一列不移位,第二列移一位,第三列移兩位,第四列移三位
  • 3.MixColumn : 把每一個行乘一個矩陣
  • 4.AddRoundKey : 讓State跟回合金鑰做XOR
  • 以上步驟進行10、12、14次,依金鑰長度而定 
4.回合金鑰如何產生?
  • 利用主金鑰產生回合金鑰
  • 每個欲加入的字元w[i]由前一個跟往前第四個字元決定
    • 若i為4的倍數,將上述兩值XOR
    • 否則將w[i-1]進行函數g運算後,再與w[i-4]做XOR
  •  函數g
    • 將w[i-1]做旋轉後與取代

6.破解AES
  • 128位元的密鑰,要2^128次
  • 差異攻擊、線性攻擊與統計攻擊對AES無效 
7.補充:Mixcolumn
  • 矩陣中相乘會不會導致state的值越來越大?
  • 思考什麼是有限體 (GF)
  • 有限體能以多項式來表示有限運算元集合
  • AES的運算是基於GF(2^8)
    • 在GF(2^8)下,加法運算被列入XOR
    • 為了使乘法有封閉性,要mod多項式x^8+x^4+x^3+x+1

2014年10月6日 星期一

時間複雜度

-Compile time :
-Execution time

     -Program step:       
   
        Definition : a program step is a syntactically meaningful program step whose execution time is independent of the instance characteristics,which means that something like the header of a sub program, a declaration of a variable (without assignment) is not consider as program step.
        Cautious : the execution time of program steps may be different,which depends on the degree of complexity.
   
    -How to ?
        -by a global variable (count) to calculate step by step.
        -by a table on counting the product of s/e(step/execution) and frequency (Fig.1.3)
       
    -So whats the different between two methods?
        -a global variable returns a number,
        -a table presents a function of time and step. e.g. 2n+n , n is a scale of input.
   
    -The best / average / worst step count.



-The big O notation:
    -Definition :   
    f(n) = O(g(n)) iff there exist positive constants c and n0 such that f(n) <= cg(n) for all n,n>=n0

-The omega notation:
    -Definition :
    f(n) = omega(g(n)) iff there exist positive constants c and n0 such that f(n) >= cg(n) for all n,n>=n0

-The theta notation:
    -Definition :
    f(n) = theta(g(n)) iff there exist positive constants c1,c2 and n0 such that c1g(n0) <=f(n)<=c2g(n) for all n,n>=n0.

-結論:
    1.O考慮的是函數上限(Upper bound),omega則考慮下限,theta則是O跟omega的夾擠
    2.取的都是最函數趨勢影響最重要的一項