Creates a signature from a private key, signs a message and ecrecover in Java. Hashes are equal to Solidity and recoverSigner works with values generated in Java in Solidity ECTools below. Uses web3j.

ECRecover.java

public class ECRecover {

	private void pkDisplay() {
		//0x627306090abaB3A6e1400e9345bC60c78a8BEf57
		String privateKey1 = "c87509a1c067bbde78beb793e6fa76530b6382a4c0241e5e4a9ec0a0f44dc0d3";
		Credentials credentials = Credentials.create(privateKey1);
		System.out.println("pk:" + Numeric.toHexStringNoPrefix(credentials.getEcKeyPair().getPublicKey()));

		String message = "now that's a text";
		String label = "\u0019Ethereum Signed Message:\n"+ String.valueOf(message.getBytes().length) + message;
		System.out.println("hash:" + Hash.sha3String(label));

		ByteBuffer buffer = ByteBuffer.allocate(label.getBytes().length);
		buffer.put(label.getBytes());
		byte[] array = buffer.array();
		Sign.SignatureData signature = Sign.signMessage(array, credentials.getEcKeyPair(), true);

		ByteBuffer sigBuffer = ByteBuffer.allocate(signature.getR().length + signature.getS().length + 1);
		sigBuffer.put(signature.getR());
		sigBuffer.put(signature.getS());
		sigBuffer.put(signature.getV());
		System.out.println("sig:" + Numeric.toHexString(sigBuffer.array()));

		ECDSASignature esig = new ECDSASignature(Numeric.toBigInt(signature.getR()), Numeric.toBigInt(signature.getS()));
		BigInteger res = Sign.recoverFromSignature(0, esig, Hash.sha3(label.getBytes()));
		System.out.println("public Ethereum address: 0x" + Keys.getAddress(res));
	}
	public static void main(String[] args) {
		new ECRecover().pkDisplay();
	}

}

ECTools.sol

pragma solidity ^0.4.18;


contract ECTools {

  // @dev Recovers the address which has signed a message
  // @thanks https://gist.github.com/axic/5b33912c6f61ae6fd96d6c4a47afde6d
  function recoverSigner(bytes32 _hashedMsg, string _sig) public pure returns (address) {
    require(_hashedMsg != 0x00);

    if (bytes(_sig).length != 132) {
      return 0x0;
    }
    bytes32 r;
    bytes32 s;
    uint8 v;
    bytes memory sig = hexstrToBytes(substring(_sig, 2, 132));
    assembly {
      r := mload(add(sig, 32))
      s := mload(add(sig, 64))
      v := byte(0, mload(add(sig, 96)))
    }
    if (v < 27) {
      v += 27;
    }
    if (v < 27 || v > 28) {
      return 0x0;
    }
    return ecrecover(_hashedMsg, v, r, s);
  }

  // @dev Verifies if the message is signed by an address
  function isSignedBy(bytes32 _hashedMsg, string _sig, address _addr) public pure returns (bool) {
    require(_addr != 0x0);

    return _addr == recoverSigner(_hashedMsg, _sig);
  }

  // @dev Converts an hexstring to bytes
  function hexstrToBytes(string _hexstr) public pure returns (bytes) {
    uint len = bytes(_hexstr).length;
    require(len % 2 == 0);

    bytes memory bstr = bytes(new string(len / 2));
    uint k = 0;
    string memory s;
    string memory r;
    for (uint i = 0; i < len; i += 2) {
      s = substring(_hexstr, i, i + 1);
      r = substring(_hexstr, i + 1, i + 2);
      uint p = parseInt16Char(s) * 16 + parseInt16Char(r);
      bstr[k++] = uintToBytes32(p)[31];
    }
    return bstr;
  }

  // @dev Parses a hexchar, like 'a', and returns its hex value, in this case 10
  function parseInt16Char(string _char) public pure returns (uint) {
    bytes memory bresult = bytes(_char);
    // bool decimals = false;
    if ((bresult[0] >= 48) && (bresult[0] <= 57)) {
      return uint(bresult[0]) - 48;
    } else if ((bresult[0] >= 65) && (bresult[0] <= 70)) {
      return uint(bresult[0]) - 55;
    } else if ((bresult[0] >= 97) && (bresult[0] <= 102)) {
      return uint(bresult[0]) - 87;
    } else {
      revert();
    }
  }

  // @dev Converts a uint to a bytes32
  // @thanks https://ethereum.stackexchange.com/questions/4170/how-to-convert-a-uint-to-bytes-in-solidity
  function uintToBytes32(uint _uint) public pure returns (bytes b) {
    b = new bytes(32);
    assembly {mstore(add(b, 32), _uint)}
  }

  // @dev Hashes the signed message
  // @ref https://github.com/ethereum/go-ethereum/issues/3731#issuecomment-293866868
  function toEthereumSignedMessage(string _msg) public pure returns (bytes32) {
    uint len = bytes(_msg).length;
    require(len > 0);
    bytes memory prefix = "\x19Ethereum Signed Message:\n";
    return keccak256(prefix, uintToString(len), _msg);
  }

  // @dev Converts a uint in a string
  function uintToString(uint _uint) public pure returns (string str) {
    uint len = 0;
    uint m = _uint + 0;
    while (m != 0) {
      len++;
      m /= 10;
    }
    bytes memory b = new bytes(len);
    uint i = len - 1;
    while (_uint != 0) {
      uint remainder = _uint % 10;
      _uint = _uint / 10;
      b[i--] = byte(48 + remainder);
    }
    str = string(b);
  }


  // @dev extract a substring
  // @thanks https://ethereum.stackexchange.com/questions/31457/substring-in-solidity
  function substring(string _str, uint _startIndex, uint _endIndex) public pure returns (string) {
    bytes memory strBytes = bytes(_str);
    require(_startIndex <= _endIndex);
    require(_startIndex >= 0);
    require(_endIndex <= strBytes.length);

    bytes memory result = new bytes(_endIndex - _startIndex);
    for (uint i = _startIndex; i < _endIndex; i++) {
      result[i - _startIndex] = strBytes[i];
    }
    return string(result);
  }
}

SignatureService.java

package hello;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.web3j.crypto.*;
import org.web3j.protocol.Web3j;
import org.web3j.utils.Numeric;

import java.math.BigInteger;
import java.nio.ByteBuffer;

public class SignatureService {

    private static Log log = LogFactory.getLog(SignatureService.class);

    public void pkDisplay(Web3j web3j, byte[] user, byte[] proof, String useraddress) throws Exception {
        String privateKey1 = "c87509a1c067bbde78beb793e6fa76530b6382a4c0241e5e4a9ec0a0f44dc0d3";
        Credentials credentials = Credentials.create(privateKey1);
        log.info("Address: " + credentials.getAddress());

        byte[] domainSep = Hash.sha3("EIP712Domain(string name,string version,uint256 chainId,address verifyingContract,bytes32 salt)".getBytes());
        byte[] akycType = Hash.sha3("AKYC(bytes32 user,bytes32 proof,address useraddress)".getBytes());
        String domainAsString = Numeric.toHexString(domainSep) +
                Numeric.toHexString(Hash.sha3("Almost KYC".getBytes())).substring(2) +
                Numeric.toHexString(Hash.sha3("2".getBytes())).substring(2) +
                Numeric.toHexStringNoPrefix(Numeric.toBytesPadded(BigInteger.valueOf(3), 32)) +
                "000000000000000000000000" + useraddress.substring(2) +
                "f2d857f4a3edcb9b78b4d503bfe733db1e3f6cdc2b7971ee739626c97e86a558";
        //"0xf2d857f4a3edcb9b78b4d503bfe733db1e3f6cdc2b7971ee739626c97e86a558", "0xf2d857f4a3edcb9b78b4d503bfe733db1e3f6cdc2b7971ee739626c97e86a558", "0xca35b7d915458ef540ade6068dfe2f44e8fa733c"
        String proofStr = Numeric.toHexStringNoPrefix(Hash.sha3(
                Numeric.hexStringToByteArray(
                        "0x1901" +
                        Numeric.toHexStringNoPrefix(Hash.sha3(Numeric.hexStringToByteArray(domainAsString))) +
                        Numeric.toHexStringNoPrefix(Hash.sha3(Numeric.hexStringToByteArray(
                                Numeric.toHexStringNoPrefix(akycType) +
                                Numeric.toHexStringWithPrefixZeroPadded(Numeric.toBigInt(user), 64).substring(2) +
                                Numeric.toHexStringWithPrefixZeroPadded(Numeric.toBigInt(proof), 64).substring(2) +
                                "000000000000000000000000" + useraddress.substring(2)))
                        ))));
        log.info("proof plain:" + proofStr);

        // sign
        Sign.SignatureData signature = Sign.signMessage(Numeric.hexStringToByteArray(proofStr), credentials.getEcKeyPair(), false);
        ByteBuffer sigBuffer = ByteBuffer.allocate(signature.getR().length + signature.getS().length + 1);
        sigBuffer.put(signature.getR());
        sigBuffer.put(signature.getS());
        sigBuffer.put(signature.getV());

        log.info(String.format("signed proof: %s", Numeric.toHexString(sigBuffer.array())));

        ECDSASignature esig = new ECDSASignature(Numeric.toBigInt(signature.getR()), Numeric.toBigInt(signature.getS()));
        BigInteger res = Sign.recoverFromSignature(0, esig, Numeric.hexStringToByteArray(proofStr));
        log.info("public Ethereum address: 0x" + Keys.getAddress(res));
    }

}

Verifier.sol

pragma experimental ABIEncoderV2;
pragma solidity ^0.4.24;

contract Verifier {
    uint256 constant chainId = 3;
    address constant verifyingContract = 0x1C56346CD2A2Bf3202F771f50d3D14a367B48070;
    bytes32 constant salt = 0xf2d857f4a3edcb9b78b4d503bfe733db1e3f6cdc2b7971ee739626c97e86a558;
    
    string private constant EIP712_DOMAIN  = "EIP712Domain(string name,string version,uint256 chainId,address verifyingContract,bytes32 salt)";
    string private constant KYC_TYPE = "AKYC(bytes32 user,bytes32 proof,address useraddress)";
    
    bytes32 private constant EIP712_DOMAIN_TYPEHASH = keccak256(abi.encodePacked(EIP712_DOMAIN));
    bytes32 private constant AKYC_TYPEHASH = keccak256(abi.encodePacked(KYC_TYPE));
    bytes32 private constant DOMAIN_SEPARATOR = keccak256(abi.encode(
        EIP712_DOMAIN_TYPEHASH,
        keccak256("Almost KYC"),
        keccak256("2"),
        chainId,
        verifyingContract,
        salt
    ));
    
    struct AKYC {
        bytes32 user;
        bytes32 proof;
        address useraddress;
    }
    
    function hashAkyc(AKYC memory akyc) private pure returns (bytes32){
        return keccak256(abi.encodePacked(
            "\x19\x01",
            DOMAIN_SEPARATOR,
            keccak256(abi.encode(
                AKYC_TYPEHASH,
                akyc.user,
                akyc.proof,
                akyc.useraddress
            ))
        ));
    }
    
    function verify(bytes32 user, bytes32 proof, address useraddress) public pure returns (bool) {
        AKYC memory akyc = AKYC({
            user: user,
            proof: proof,
            useraddress: useraddress
        });
            
        bytes32 sigR = 0x7c8183f05935acce8e0923c70670a5d46409a78183ab206e49182f6f16053b56;
        bytes32 sigS = 0x620674604996ed0606ac322eb1dcdabf814372c7e841e72f1629520e4b35a904;
        uint8 sigV = 27;
        address signer = 0x627306090abab3a6e1400e9345bc60c78a8bef57;
    
        return signer == ecrecover(hashAkyc(akyc), sigV, sigR, sigS);
    }
}

SignatureService is an EIP712 compliant check in Java. Verifier.sol is the verifying contract.