2017-10-06

ed25519のpython実装を紐解くその１数学編

ed25519

ed25519のpythonによるリファレンス実装を解説してみます。
pythonのリファレンス実装はこちらです。
https://ed25519.cr.yp.to/python/ed25519.py

数学的な関数の解説のみ簡単に行います。
詳しくはこのブログの他の記事に記載があります。
使う楕円曲線はed25519と呼ばれる、Twisted Edward曲線です。

q = 2**255 - 19
L = 2**252 + 27742317777372353535851937790883648493

素数2²⁵⁵-19=57896044618658097711785492504343953926634992332820282019728792003956564819949
=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
は10進数で77桁の素数です。
曲線の方程式は $- {x}^{2} + {y}^{2} = 1 - \frac {121665} {121666} {x}^{2} {y}^{2}$ という形をしており、xが一つ決まるとyが一つ決まりますが、x,yは共に整数しか取りません。
そして、 $- \frac {121655} {121666}$ は分数ではなく整数であり、
$- \frac {121655} {121666}$ = 37095705934669439343138083508754565189542113879843219016388785533085940283555 という10進数で77桁の整数です。
この方程式は素数qを法とし成り立つものとして考えます。
なぜ割り算で表現してあるかというと、その方が77桁の整数を全てを書くよりも紙面が節約できるからです。
なぜ割り算がこうなるのかというと、素数を法とした演算を使うと体を成すことが知られているためです。
これを素体といいます。
整数の範囲内での演算なので、割り算は掛け算を使って表現します。

LはこちらのRFC8032
RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
に書かれている通り、 ed255199曲線の有理点の数(#Eと表現します。)の約数である素数であり、
$L = {2}^{252} + 27742317777372353535851937790883648493$
= 7237005577332262213973186563042994240857116359379907606001950938285454250989
= 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
という10進で76桁の整数です。
なお、 $8 L = \#E$ です。
Hasse-Weilの定理を考えると、有理点の数がこのくらいあることは納得感があります。
つまり有理点の数は10進で77桁くらいあるということです。(※1)
また、このLはある条件を満たしますが、これは後で説明します。

def expmod(b,e,m):
  if e == 0: return 1
  t = expmod(b,e/2,m)**2 % m
  if e & 1: t = (t*b) % m
  return t

expmod関数では高速指数計算法で法mにおいてbのe乗を計算する関数です。

def inv(x):
  return expmod(x,q-2,q)

inv関数では法qにおけるxの逆数を計算する関数です。
なぜq-2乗すると逆数になるのかはオイラーの小定理を考えると理解できます。

d = -121665 * inv(121666)

そのままですね。

I = expmod(2,(q-1)/4,q)

これは、ここで平方剰余を計算するときのケースAのときの係数です。

mod pでの平方剰余を計算する(p mod 8 = 5の場合)を実装する - Pebble Coding

def xrecover(y):
  xx = (y*y-1) * inv(d*y*y+1)
  x = expmod(xx,(q+3)/8,q)
  if (x*x - xx) % q != 0: x = (x*I) % q
  if x % 2 != 0: x = q-x
  return x

xrecovery関数は、曲線上のyの値が与えられたときにxの値を求める関数です。
単純にed25519の方程式をxについてまとめると最初の式になり、 ${x}^{2} = a$ を解く形になります。
この解き方は先ほどのリンクで説明しています。
xが奇数になったときは、奇素数qを使って反転して、q(奇数)-x(奇数) = 偶数に変換しています。
xが解であるとき、q-xが解であることは、
${(q-x)}^{2} = {q}^{2} - 2qx + {x}^{2} = {x}^{2} \mod q$ であることから分かります。

By = 4 * inv(5)
Bx = xrecover(By)
B = [Bx % q,By % q]

これもRFCに記載されていますが、ベースポイントの座標です。実際の値は次のような値です。
Bx = 15112221349535400772501151409588531511454012693041857206046113283949847762202
77桁の10進数

By = 46316835694926478169428394003475163141307993866256225615783033603165251855960
77桁の10進数

ベースポイントBとは点のスカラー倍を計算していくときの最初の点です。
点BをLスカラー倍したときにゼロ点(x=0, y=1)になります。
通常の楕円曲線ではゼロ点は無限遠点ですが、この曲線ではこのような有限の値の点になるので、
コンピュータでの計算が分かりやすくなっています。
Lは最初の方で出てきた値です。
つまり $L B = 0$ と表現できます。点Bの位数はLであるともいいます。

これらの条件は、楕円曲線暗号において知られている攻撃方法を回避するように設定されています。
新たな攻撃方法が発見されない限り、安全だと言えます。

def edwards(P,Q):
  x1 = P[0]
  y1 = P[1]
  x2 = Q[0]
  y2 = Q[1]
  x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)
  y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2)
  return [x3 % q,y3 % q]

edwards関数では点Pと点Qを加算した点の座標を求めています。

def scalarmult(P,e):
  if e == 0: return [0,1]
  Q = scalarmult(P,e/2)
  Q = edwards(Q,Q)
  if e & 1: Q = edwards(Q,P)
  return Q

scalarmult関数では点Pをe倍した点の座標を求めます。
これは、倍数を高速に計算する方法を再帰で実装したものです。このリンク
高速指数計算法アルゴリズム - Pebble Coding
ではべき乗の場合ですが、倍数の場合も同じようなロジックになります。

def isoncurve(P):
  x = P[0]
  y = P[1]
  return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0

isoncurve関数は点Pが楕円曲線上にあるかどうかを返す関数です。

ここでみたように楕円曲線暗号は初等整数論、楕円関数論を活用して作られていることが分かります。
大学の数学科4年生レベルの数学知識が求められ、理解するのに一筋縄ではいきません。

※1 この有理点の数を求めるのにどのくらい時間がかかるのか想像できていません。
mac book proでは数分レベルでないことは分かっていますが、誰か調べて欲しい。。

ed25519のpython実装を紐解くその２暗号編キーペア生成からベリファイまで - Pebble Coding

2017-10-05

Twisted Edward曲線における加法

ed25519

Twisted Edward曲線 $- x^{2} + y^{2} = 1 + d x^{2}y^{2}$

において、曲線上の２つの点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ の加算後の点を次のように定義する。

$\displaystyle X = \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + d x_{1} x_{2} y_{1} y_{2}}$

$\displaystyle Y = \frac {x_{1} x_{2} + y_{1} y_{2}} {1 - d x_{1} x_{2} y_{1} y_{2}}$

この点は代数計算によって、Twisted Edward曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。
計算のコツとしては常に $x_{1} x_{2} y_{1} y_{2}$ の順序でまとめておくことである。　　

$A = - X^{2} + Y^{2} - d X^{2}Y^{2}$ を計算し、 $1$ に等しくなることを示す方針で行く。

代入すると $\displaystyle A = \frac {1} {(1 + d x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - d x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ - (x_{1}y_{2} + x_{2}y_{1})^{2}(1- d x_{1}x_{2}y_{1}y_{2})^{2} \\ + (x_{1}x_{2} + y_{1}y_{2})^{2} (1 + d x_{1} x_{2} y_{1} y_{2})^{2} \\ - d (x_{1}y_{2} + x_{2}y_{1})^{2} (x_{1}x_{2} + y_{1}y_{2})^{2})$

ここで、

$\displaystyle A(1 - d^{2} x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2})^{2} = B + C + D$ と置く。

B + C + Dを全て展開し、 $x_{1}, x_{2}, y_{1}, y_{2}$ の順番で並べると、７つほどペアが消える。

$B + C + D = - x_{1}^{2}y_{2}^{2} - x_{2}^{2}y_{1}^{2} + x_{1}^{2} x_{2}^{2} + y_{1}^{2} y_{2}^{2} \\ - d x_{1}^{4}x_{2}^{2}y_{2}^{2} - d x_{1}^{2}x_{2}^{4}y_{1}^{2} - d x_{1}^{2}y_{1}^{2}y_{2}^{4} - d x_{2}^{2}y_{1}^{4}y_{2}^{2} + 4 d x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} \\ - d^{2} x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} - d^{2} x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} + d^{2} x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} + d^{2} x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} \\ = E_{4} + E_{8} + E_{12}$

ここで $E_{i}$ はx,yの個数を表すが、それぞれ別々に計算してゆくと、 $E_{4}, E_{8}, E_{12}$ には、 $- x_{1}^{2} + y_{1}^{2}$ , $- x_{2}^{2} + y_{2}^{2}$ が２つ以上出てくるので、 $- x_{1}^{2} + y_{1}^{2} = 1 + d x_{1}^2 y_{1}^2$
$- x_{2}^{2} + y_{2}^{2} = 1 + d x_{2}^2 y_{2}^2$ に置き換える。

ここで、 $E_{4} + E_{8} + E_{12}$ を計算すると、 $1 - 2 d^{2} x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + d^{4} x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}$ が残る。あとは自明である。

2017-09-23

swift3でCoreAudioを使う録音編

swift オーディオプログラミング

CoreAudio/swift3で録音を行うサンプルです。
iPhoneのマイクから取得した音声データをレベル値に変換して画面に表示します。

import Foundation
import AVFoundation
import AudioUnit

class MyAudioRecorder: NSObject {
    var level: Float  = 0.0
    var frameCount: UInt32 = 0

    private var _audioUnit: AudioUnit?   
    private var _abl: AudioBufferList?
    private let kInputBus: UInt32 =  1
    private let kNumberOfChannels: Int =  1
    
    func start() {
        // AudioSession セットアップ
        do {
            let audioSession = AVAudioSession.sharedInstance()
            try audioSession.setCategory(AVAudioSessionCategoryRecord)            
            try audioSession.setActive(true)
        } catch {
        }
        // CoreAudio セットアップ
        var componentDesc:  AudioComponentDescription
            = AudioComponentDescription(
                componentType:          OSType(kAudioUnitType_Output),
                componentSubType:       OSType(kAudioUnitSubType_RemoteIO),
                componentManufacturer:  OSType(kAudioUnitManufacturer_Apple),
                componentFlags:         UInt32(0),
                componentFlagsMask:     UInt32(0) )
        
        let component: AudioComponent! = AudioComponentFindNext(nil, &componentDesc)
        var tau: AudioUnit?
        AudioComponentInstanceNew(component, &tau)
        _audioUnit = tau
        
        guard let au = _audioUnit else { 
            return
        }
        // RemoteIO のマイクを有効にする
        var enable: UInt32 = 1
        AudioUnitSetProperty(au,
                             kAudioOutputUnitProperty_EnableIO,
                             kAudioUnitScope_Input,
                             kInputBus,
                             &enable,
                             UInt32(MemoryLayout<UInt32>.size))

        // マイクから取り出すデータフォーマット
        // 32bit float, linear PCM
        guard let fmt = AVAudioFormat(standardFormatWithSampleRate: 44100, 
                                      channels: UInt32(kNumberOfChannels)) else {
            return
        }
        
        // RemoteIO のマイクバスから取り出すフォーマットを設定
        AudioUnitSetProperty(au,
                             kAudioUnitProperty_StreamFormat,
                             kAudioUnitScope_Output,
                             kInputBus,
                             fmt.streamDescription,
                             UInt32(MemoryLayout<AudioStreamBasicDescription>.size))

        // AudioUnit に録音コールバックを設定
        var inputCallbackStruct
            = AURenderCallbackStruct(inputProc: recordingCallback,
                                     inputProcRefCon:
                UnsafeMutableRawPointer(Unmanaged.passUnretained(self).toOpaque()))
        AudioUnitSetProperty(au,
                             AudioUnitPropertyID(kAudioOutputUnitProperty_SetInputCallback),
                             AudioUnitScope(kAudioUnitScope_Global),
                             kInputBus,
                             &inputCallbackStruct,
                             UInt32(MemoryLayout<AURenderCallbackStruct>.size))
        
        // データ取り出し時に使う AudioBufferListの設定
        _abl = AudioBufferList(
            mNumberBuffers: 1,
            mBuffers: AudioBuffer(
                mNumberChannels: fmt.channelCount,
                mDataByteSize: fmt.streamDescription.pointee.mBytesPerFrame,
                mData: nil))

        AudioUnitInitialize(au)
        AudioOutputUnitStart(au)
    }
    
    let recordingCallback: AURenderCallback = { (
        inRefCon,
        ioActionFlags,
        inTimeStamp,
        inBusNumber,
        frameCount,
        ioData ) -> OSStatus in
        
        let audioObject = unsafeBitCast(inRefCon, to: MyAudioRecorder.self)

        if let au = audioObject._audioUnit {
            // マイクから取得したデータを取り出す
            AudioUnitRender(audioObject._audioUnit!,
                                ioActionFlags,
                                inTimeStamp,
                                inBusNumber,
                                frameCount,
                                &audioObject._abl!)
        }
        audioObject.frameCount = frameCount
        let inputDataPtr = UnsafeMutableAudioBufferListPointer(&audioObject._abl!)
        let mBuffers: AudioBuffer = inputDataPtr[0]
        let bufferPointer = UnsafeMutableRawPointer(mBuffers.mData)
        if let bptr = bufferPointer {
            let dataArray = bptr.assumingMemoryBound(to: Float.self)
            // マイクから取得したデータからRMS(RootMeanSquare)レベルを計算する
            var sum:Float = 0.0
            if frameCount > 0 {
                for i in 0 ..< Int(frameCount) {
                    sum += (dataArray[i]*dataArray[i])
                }
                audioObject.level = sqrt(sum / Float(frameCount))
            }
        }
        return 0
    }
}

まず、Info.plistに
Privacy - Microphone Usage Description
の項目を追加します。
これを行わないとiPhoneのマイクが使えません。

次に、オーディオセッションのカテゴリを録音にします。

let audioSession = AVAudioSession.sharedInstance()
try audioSession.setCategory(AVAudioSessionCategoryRecord)            
try audioSession.setActive(true)

録音を行う RemoteIO を作り、RemoteIO のマイクを有効にします。

マイクから取り出すデータフォーマットを設定します。
ここでは、32bit float モノラルサンプルレート44.1kHzとしました。 RemoteIOに録音コールバック関数を設定します。

録音を開始すると、例えば1024サンプル録音される毎にこのコールバック関数が呼ばれるので、コールバック関数内でバッファからデータを取り出して処理します。

ここでは、取り出したデータの平均値(RMS)を計算します。
ViewController上にはこの値を画面に表示しています。

以下、ViewController のソースです。

class ViewController: UIViewController {
    @IBOutlet var progress:UIProgressView!
    @IBOutlet var label:UILabel!
    
    var recorder:MyAudioRecorder!
    var timer: Timer!
    override func viewDidLoad() {
        super.viewDidLoad()
        recorder = MyAudioRecorder()
        recorder?.start()
    }
    
    override func viewWillAppear(_ animated: Bool) {
        super.viewWillAppear(animated)
        timer = Timer.scheduledTimer(timeInterval: 0.005, target: self, selector: #selector(self.update), userInfo: nil, repeats: true)
        timer.fire()
    }
    
    override func viewWillDisappear(_ animated: Bool) {
        super.viewWillDisappear(animated)
        timer.invalidate()
    }
    
    @objc func update(tm: Timer){
        progress.progress = recorder.level
        label.text = "\(recorder.frameCount)"
    }    
}